Текст раз
Этот пост посвящен игрушечному алгоритму автоматической генерации названий городов.
Задача: придумать географическую карту некоторого воображаемого (например, игрового) мира. С городами, реками, озерами, горами, и прочими интересными местами. Условно можно выделить две подзадачи: размещение объектов и выдача объектам имён — чтобы отличать их друг от друга (скажем, при выдаче заданий игроку). Расположение этих объектов на карте может быть продиктовано дополнительными условиями в задаче, или же их можно сгенерировать одним из известных алгоритмов генерации местности, в этом посте нас интересует вторая под задача — выдача объектам имён. Идейно правильный метод её решения — проработка истории, культуры и языка нашего воображаемого мира. Если наш мир генерируется случайно, то вряд ли мы сможем программно сгенерировать всю его историю, культуру и язык — если, разумеется, мы не имеем дело с Dwarf Fortress.
Дальше, конкретики ради, сфокусируемся на названиях городов: требуется придумать алгоритм, который бы мог генерировать имена городов, звучащих «схоже». (Требование «схожести» означает, что, увы, мы не можем просто случайно комбинировать буквы и слоги).
«Знаешь, как получаются новые имена персонажей?» — спросил меня однажды знакомый во время партии в карточную игру Берсерк. Ответа я не знал. «Они идут в аптеку, переписывают этикетки, а потом перемешивают слоги». Я тогда усмехнулся, но вскоре, к своему удивлению, стал замечать, что имена некоторых фэнтезийных персонажей подозрительно напоминают мне названия обезболивающих.
Отталкиваясь от этой идеи и идеи использования марковских цепей для генерации случайных шизофазических текстов, можно придумать такой игрушечный алгоритм генерации:
Здесь «схожесть» понимается как «узнаваемость» исходного языка. Хороший результат работы алгоритма на, скажем, немецких городах, должен, во-первых, отличаться от каждого из городов в исходном списке, и, во-вторых, он должен «визуально» выглядеть «немецким».(«Дырдырдырштрассе» — «Хм! Похоже на улицу в Германии!»).
Сказано — сделано.
Практика показала, что комбинации в 2 буквы дают дикую мешанину, комбинации в 5 букв дают имена, мало отличающиеся от исходных, а 3-4 буквы дают весьма неплохие результаты, которые, впрочем, всё равно приходится фильтровать дополнительными критериями (вроде невозможности начала слова с мягкого знака или дефиса).
А теперь, собственно, результаты.
Первым подопытным языком стал, естественно, русский. Имея список из 321 городов РФ, программа после пары запусков выдала, в том числе, вот такие правдоподобные названия:
Помимо этого, были и довольно занятные имена, вроде следующих:
Впрочем, встречается изрядно «паразитных» имён, которых приходится фильтровать отдельно, например:
Следующим языком стал немецкий (список из 511 городов), и, признаться, на нём алгоритм отработал лучше всего: меньшего всего брака и больше всего «культурной узнаваемости»:
Занятно, что алгоритм перенял некоторую особенность немецкого языка, в топонимах не просматривающуюся, выдавая названия вроде:
Затем настал черед ирландского языка (384 городов):
В целом результаты где-то между русским и немецким по разнообразию и узнаваемости. Кроме того, алгоритм предложил города с названиями «Орк» и «Маг».
Потом был протестирован китайский (343 города) :
Здесь генератор отработал хуже всего: почему-то большинство сгенерированных названий либо слабо отличаются от имеющихся названий, либо представляют сущее нагромождение букв. Генератор также выдал город, отлично подходящий для рассказа о Ктулху: «Нгчангфангган».
Наконец, последним был взят список городов из Бразилии (485 штук):
Любовь к длинным и сложным названиям городов дала возможность генератору выдавать самый широкий спектр названий, что, увы, сказалось на «узнаваемости». Впрочем, было и нечто забавное:
Итак, по уровню применимости нашего игрушечного алгоритма я бы отсортировал языки так: немецкий, ирландский, русский/бразильсикй, китайский.
Интересно, конечно, оценить, насколько сгенерированные названия режут слух людям, действительно знающим соответствующие языки. Например, мне большая часть сгенерированного русского звучит страшно непривычно.
Теперь моя голова занята судьбами отважных инженеров из Напаянска, страшной тайной замка Дауншварцвальдесхейлиген и тёмными ужами бездны Нгчангфанггана.
Задача: придумать географическую карту некоторого воображаемого (например, игрового) мира. С городами, реками, озерами, горами, и прочими интересными местами. Условно можно выделить две подзадачи: размещение объектов и выдача объектам имён — чтобы отличать их друг от друга (скажем, при выдаче заданий игроку). Расположение этих объектов на карте может быть продиктовано дополнительными условиями в задаче, или же их можно сгенерировать одним из известных алгоритмов генерации местности, в этом посте нас интересует вторая под задача — выдача объектам имён. Идейно правильный метод её решения — проработка истории, культуры и языка нашего воображаемого мира. Если наш мир генерируется случайно, то вряд ли мы сможем программно сгенерировать всю его историю, культуру и язык — если, разумеется, мы не имеем дело с Dwarf Fortress.
Дальше, конкретики ради, сфокусируемся на названиях городов: требуется придумать алгоритм, который бы мог генерировать имена городов, звучащих «схоже». (Требование «схожести» означает, что, увы, мы не можем просто случайно комбинировать буквы и слоги).
«Знаешь, как получаются новые имена персонажей?» — спросил меня однажды знакомый во время партии в карточную игру Берсерк. Ответа я не знал. «Они идут в аптеку, переписывают этикетки, а потом перемешивают слоги». Я тогда усмехнулся, но вскоре, к своему удивлению, стал замечать, что имена некоторых фэнтезийных персонажей подозрительно напоминают мне названия обезболивающих.
Отталкиваясь от этой идеи и идеи использования марковских цепей для генерации случайных шизофазических текстов, можно придумать такой игрушечный алгоритм генерации:
- Взять список реальных имён городов какого-нибудь региона или страны;
- Посчитать статистику по этому списку: с какой вероятностью одни комбинации букв следуют за другими;
- Сгенерировать случайные имена, полученные склеиванием комбинаций букв, починяющиеся полученной статистике.
Здесь «схожесть» понимается как «узнаваемость» исходного языка. Хороший результат работы алгоритма на, скажем, немецких городах, должен, во-первых, отличаться от каждого из городов в исходном списке, и, во-вторых, он должен «визуально» выглядеть «немецким».(«Дырдырдырштрассе» — «Хм! Похоже на улицу в Германии!»).
Сказано — сделано.
Практика показала, что комбинации в 2 буквы дают дикую мешанину, комбинации в 5 букв дают имена, мало отличающиеся от исходных, а 3-4 буквы дают весьма неплохие результаты, которые, впрочем, всё равно приходится фильтровать дополнительными критериями (вроде невозможности начала слова с мягкого знака или дефиса).
А теперь, собственно, результаты.
Первым подопытным языком стал, естественно, русский. Имея список из 321 городов РФ, программа после пары запусков выдала, в том числе, вот такие правдоподобные названия:
- Бугулев
- Чессесск
- Кровичи
- Вантатеевка
- Кирирово
- Бововещенск
- Кататский Тагадан
- Таймайкопейск
- Ошкарино
- Перопавль
- Еверь
- Турьинск
- Судженск-на-Кубани
- Напаевск
Помимо этого, были и довольно занятные имена, вроде следующих:
- Куйбуйбышевск
- Лологда
- Cахачкалин
- Гусь-хрустальные водск
- Усь-хрусть-илимск
- Юбербаш
- Охладивострахангарск
- Едринбургань
Впрочем, встречается изрядно «паразитных» имён, которых приходится фильтровать отдельно, например:
- Иноно-сахачкалуга
- Лнлны
- -хрхрус-манск
- -уральчик
- Ь-илимск
- Бебережные Челябинск
- Брьскитимашевсковочерезникие лук
- Нскск
Следующим языком стал немецкий (список из 511 городов), и, признаться, на нём алгоритм отработал лучше всего: меньшего всего брака и больше всего «культурной узнаваемости»:
- Аугсбург
- Абрюкенхайм
- Руттинг
- Ипфенбург
- Ласфельбек
- Мюльхаген
- Фленсхафен
- Ведлинг
- Варцвалькен
- Ратценхайм
- Риттельбронн
- Обрунн
- Хоккернау
- Деценбург
- Фельдернау
Занятно, что алгоритм перенял некоторую особенность немецкого языка, в топонимах не просматривающуюся, выдавая названия вроде:
- Эрнстехудесхеймарнсбург
- Дауншварцвальдесхейлиген
- Изеебад-кюлунгенфильмюнстерслар
- Рцартенауберг-бухгольсбюльхофен
- Вольтауншвангентерлингенхайм
- Одтнауэшингеранкфурт-на-одербург-на-майн
Затем настал черед ирландского языка (384 городов):
- Анкилбридж
- Рвиллтаун
- Аппоквин
- Керриффорт
- Тарберин
- Лихис
- Руклегган
- Делгарван
- Рогвелл
- Ильтон
- Илмукридж
В целом результаты где-то между русским и немецким по разнообразию и узнаваемости. Кроме того, алгоритм предложил города с названиями «Орк» и «Маг».
Потом был протестирован китайский (343 города) :
- Айгоу
- Пуянь
- Алетайчжоу
- Хиксинай
- Жуань
- Чонгрен
- Джининде
- Мешаньян
- Женьяньинь
- Янфанчжоу
- Чонгхе
Здесь генератор отработал хуже всего: почему-то большинство сгенерированных названий либо слабо отличаются от имеющихся названий, либо представляют сущее нагромождение букв. Генератор также выдал город, отлично подходящий для рассказа о Ктулху: «Нгчангфангган».
Наконец, последним был взят список городов из Бразилии (485 штук):
- Амадор
- Имирингуарес
- Атерика
- Жакутинс
- Рападора
- Вель-де-рианейранде
- Кларолис
- Мартинга
- Претос
- Сан-Виста
- Майракапараба
Любовь к длинным и сложным названиям городов дала возможность генератору выдавать самый широкий спектр названий, что, увы, сказалось на «узнаваемости». Впрочем, было и нечто забавное:
- Киску
- Имперуйя
- Я формоза
- Ипато Афонсо Кларолиньем
- Е-санту-ду-ду-прету-амарес
Итак, по уровню применимости нашего игрушечного алгоритма я бы отсортировал языки так: немецкий, ирландский, русский/бразильсикй, китайский.
Интересно, конечно, оценить, насколько сгенерированные названия режут слух людям, действительно знающим соответствующие языки. Например, мне большая часть сгенерированного русского звучит страшно непривычно.
Теперь моя голова занята судьбами отважных инженеров из Напаянска, страшной тайной замка Дауншварцвальдесхейлиген и тёмными ужами бездны Нгчангфанггана.
@музыка: Kraftwerk --- Trans Europa Express
@темы: питон, простойный пост