Многим известна такая старая добрая игра со словами, сделать из мухи слона. Суть её в том, что нужно из начального слова сделать конечное, на каждом шаге меняя только одну букву, получая при этом на каждом шаге осмысленное существительное.
Известный автор книг по занимательной математике Е. Я. Гик в своей книге "Занимательные математические игры" опубликовал такое 16-ходовое решение, как из мухи сделать слона: муха-мура-тура-тара-кара-каре-кафе-кафр-каюр-каюк-крюк-упюк-урок-срок-сток-стон-слон.
И вот, в один прекрасный день мне довелось заняться решением этой задачи в программном виде.
Из мухи слона, первая версия
Честно признаться, слона из мухи получилось сделать довольно быстро.
Общая идея решения:
— взять словарь существительных
— итеративным алгоритмом пройти от исходного слова в сторону конечного, если получится достичь последнего
— выдать результирующую цепочку, и желательно чтоб она стремилась к минимальной длине
Итак…
1) Словарь существительных
Оказалось, даже с первым пунктом есть проблемы, — найти стоящий словарь существительных оказалось уже отдельной подзадачей. Не помню где именно, но нашёл сносный готовый словарь. Формат по одному слову на строку, utf8, разделители \r\n — так и оставил в дальнейшем.
2) Алгоритм
Естественно, походя поинтересовался решали ли эту проблему мух и слонов, и как. Хороший вариант решения нашёл тут
planetcalc.ru/544. Для только 4 буквенных слов, под яваскрипт (что на самом деле идея правильная для этого приложения — нет смысла гонять серверные мощности, когда поиском может заняться клиентское железо в браузере). Впрочем, исходники не смотрел, а смотрел на здравые рассуждения ниже в статье.
Действительно, если в качестве алгоритма использовать построение дерева со всеми вариантами, пока при прокладке очередного уровня не попадётся искомое слово, то никаких ресурсов не хватит.
Например, у слова КОРА есть 19 переходов только из распространённых слов, пришедших на ум, от «гора» до «корт».
Даже если дать очень оптимистичную оценку на среднее число вариантов модификаций в 5 (всего!), то если к какому-то слову минимальный путь составит 10 шагов, то в памяти должно уместиться дерево в 510 ~= 10 млн нодов. Учитывая накладные расходы на содержание структуры дерева (как минимум, 2 указателя на потомков из предка каждый по 4/8 байт) и на собственно хранение данных нод (языковая/структурная обёртка переменной + сами данные: символы строки в utf8 ещё более 10 байт) получим требование по ОЗУ для таких условий минимум порядка 200-300 Мб. А условия могут быть гораздо хуже.
Выбран генетический алгоритм.
Тем более он тут просто напрашивается — изменение буквы в слове это по сути мутация. Условие выживания потомка при «родах» — существование в словаре. Условие успешности конкуренции, приспособленности — степень схожести с искомым словом.
Функция генетического поиска цепочки переходов слов
/**
* Поиск цепочки побуквенных преобразований от первого слова ко второму
*
* Возвращает список слов или пустой массив если цепочки преобразований не существует
*
* @param string $wordFrom - Начальное слово
* @param string $wordTo - Конечное слово
* @return array Список слов от начального к конечному
* @throws WordWizardException
*/
public function FindMutationChain($wordFrom, $wordTo, $maxSteps = 1000, $maxPopulation = 100)
{
$resultKeysChain = [];
$resultChain = [];
// Принудительно приводим к нижнему регистру входные слова
$wordFrom = mb_convert_case($wordFrom, MB_CASE_LOWER);
$wordTo = mb_convert_case($wordTo, MB_CASE_LOWER);
$fromLen = mb_strlen($wordFrom);
$toLen = mb_strlen($wordTo);
// Слова должны быть одной длины
if ($fromLen != $toLen) {
throw new WordWizardException("Слова должны быть одинаковой длины.");
}
// Существование первого слова в словаре для алгоритма не обязательно
$wordFromKey = binary_search($this->_dictionary, $wordFrom);
// Но для второго слова, для простоты, будем это требовать
$wordToKey = binary_search($this->_dictionary, $wordTo);
if ($wordToKey < 0) {
throw new WordWizardException("Конечное слово \"$wordTo\" не обнаружено в словаре.");
}
// Инициализируем цепочку слов
$mutationChains = [ [ 'keys' => [$wordFromKey], 'mutatedPositions' => [-1] ] ];
$population = 1;
// Главный цикл генетического алгоритма поиска
for ($step = 0; $step < $maxSteps; $step++) {
// Не дошли ли до искомого слова?
foreach ($mutationChains as $mutationChain) {
if (end($mutationChain['keys']) == $wordToKey) {
// Найдена одна из кратчайших (для этого забега) цепочек
$resultKeysChain = $mutationChain['keys'];
break 2;
}
}
// Выращиваем следующее поколение
$newMutationChains = [];
foreach ($mutationChains as $mutationChain) {
$lastKey = end($mutationChain['keys']);
$lastMutatedPos = end($mutationChain['mutatedPositions']);
$lastWord = $this->_dictionary[$lastKey];
$nextMutations = $this->FindMutationVariants($lastWord, $wordTo, $fromLen, $lastMutatedPos, $mutationChain['keys']);
foreach ($nextMutations as $mutation) {
list($nextKey, $nextMutatedPos) = $mutation;
$nextWord = $this->_dictionary[$nextKey];
$score = $this->GetWordScore($nextWord, $wordTo);
// Новый потомок
$newMutationChain = $mutationChain;
$newMutationChain['keys'][] = $nextKey;
$newMutationChain['mutatedPositions'][] = $nextMutatedPos;
$newMutationChain['score'] = $score;
$newMutationChains[] = $newMutationChain;
}
}
// Предыдущее поколение больше не требуется
$mutationChains = $newMutationChains;
// А если нового не появилось..
if (empty($mutationChains)) {
throw new WordWizardException("На шаге $step (из максимально $maxSteps) закончились варианты. Поиск не увенчался успехом.");
}
// Сортируем новое поколение по "степени приспособленности" (похожести последнего слова цепочки на искомое)
usort($mutationChains, function($a, $b) {
return $b['score'] - $a['score'];
});
// Естественный отбор - оставляем самых лучших
array_splice($mutationChains, $maxPopulation);
}
// слишком глубокий поиск?
if ($step == $maxSteps) {
throw new WordWizardException("Пройдено максимально разрешённое число шагов ($maxSteps), но поиск не увенчался успехом.");
}
// Формируем итоговую цепочку из слов
if ($resultKeysChain) {
foreach ($resultKeysChain as $key) {
$resultChain[] = $this->_dictionary[$key];
}
}
return $resultChain;
}
Весовую функцию честно взял с описания на том же
planetcalc.ru/544. Обмыслил почему оно такое, для себя понял так:
— идентичность букв на верных позициях 3 балла: Без комментариев, максимальный балл тут логичен
— гласная, пусть и другая, в нужной позиции 2 балла: Гласную в нужное место гораздо труднее подтащить, зато она потом с помощью мутаций согласных, а таких вариантов больше, легче смутирует уже в нужную гласную. К тому же гласная «задаёт тон» — около неё легче крутятся согласные, в том числе нужные под искомое слово.
— наличие гласной вообще 1 балл: Схожие рассуждения с приведёнными выше, гласную мутировать значительно труднее чем согласные.
Отдельно замечу, что на всём этапе поиска эталонное слово, которое должно получиться и с которым идёт постоянное сравнение, одно и то же. Например тот же слон. Потому «разобранного на куски для сравнения слона» (бедная зверушка) логично в таком анатомическом виде и закэшировать.
Для простоты и недолго думая, соорудил простейший кэш прямо в функции оценки.
Функция оценки похожести пары слов
/**
* Функция оценки похожести слова
*
* @param string $word - Оцениваемое слово
* @param string $comparationWord - Эталонное слово
* @return int
*/
public function GetWordScore($word, $comparationWord)
{
// Частый случай поиска - с одним и тем же эталонным словом, - используем кэширование
static $cachedComparationWord = '';
static $wordLen = 0;
static $cwLetters = [];
if ($cachedComparationWord != $comparationWord) {
$cachedComparationWord = $comparationWord;
$wordLen = mb_strlen($comparationWord);
$cwLetters = [];
for ($i = 0; $i < $wordLen; $i++) {
$letter = mb_substr($comparationWord, $i, 1);
$cwLetters[$i] = [
'letter' => $letter,
'isVovel' => false === mb_strpos($this->_vovels, $letter) ? false : true,
];
}
}
$score = 0;
for ($i = 0; $i < $wordLen; $i++) {
$letter = mb_substr($word, $i, 1);
// Полностью совпадающим символам максимальная оценка = 3
if ($letter == $cwLetters[$i]['letter']) {
$score += 3;
continue;
}
$isVovel = (false === mb_strpos($this->_vovels, $letter) ? false : true);
if ($isVovel) {
if ($cwLetters[$i]['isVovel']) {
// Совпадение позиции гласной буквы = 2
$score += 2;
}
else {
// Наличие гласной буквы = 1
$score += 1;
}
}
}
return $score;
}
Поиск
новых вариантов мутаций идёт по словарю и подсловарям, отталкиваясь от заданного слова. При этом есть несколько дополнительных логических ограничений.
Первое ограничение — это допустимые позиции букв для мутации. В самом деле, если на прошлом шаге мы, например, поменяли 3-ю буквы, сделав ход «муХа» — «муЗа», то на следующем шаге мутация «муЗа» — «муРа» лишена смысла. Ведь нам интересна максимально короткая цепочка. А так мы получается делаем заведомо лишний шаг, ведь можно было сразу сделать ход «муХа» — «муРа». Поэтому одним из параметров функции является позиция прошлой мутации.
Второе ограничение — это уникальность слов в цепочке. Объясняется тоже просто. Допустим, есть цепочка «муха» — "мука" — «бука» — «бура» — «мура» — "мука" — «рука». Очевидно, что кусок "мука" — «бука» — «бура» — «мура» был лишним в цепочке. И даже если она дойдёт до финального искомого «слона», то ровно такая же, но цепочка из уникальных слов с выкинутыми повторами будет короче. А значит лучше. Так что такие циклы из-за повторов нам не нужны. Поэтому ещё одним из параметров функции поиска вариантов мутаций делаем массив слов (в данном случае id слов), которые уже были использованы в цепочке.
Параметр длины слова — это я на спичках mb_strlen поэкономил. Так-то метод задумывался приватным, но для проб и тестов был опубличен. Не пускайте такие штуки в продакшн :) Во всяком случае, без охватывающих проверок.
А конечное слово… может человеческая рефлексия какая-то, а может и интуиция, — оставил возможность использования на потом. Всё же логично ожидать от функции получения набора потомков какой-то зависимости от того, на кого похожими они должны получаться. Ничто не мешает делать первичный отсев прямо тут. Но пока — не используется.
Функция получения возможных мутаций
/**
* Получение списка пар {id слова, позиция мутации символа} для возможных вариантов мутаций
*
* Для поиска используется рабочий словарь плюс общие вспомогательные словари
*
* @param string $wordFrom - Начальное слово
* @param string $wordTo - Конечное слово
* @param int $wordLen - Длина обоих слов
* @param int $disabledMutationPos - Индекс в слове буквы, которую не нужно менять (была изменена на предыдущем шаге)
* @param array $excludedWordKeys - Уже использованные слова
* @return array
*/
public function FindMutationVariants($wordFrom, $wordTo, $wordLen, $disabledMutationPos, $excludedWordKeys)
{
$variants = [];
for ($mutPos = 0; $mutPos < $wordLen; $mutPos++) {
// Пропускаем исключённую букву (нет смысла менять ту же, что на пред. шаге)
if ($mutPos == $disabledMutationPos) continue;
// Получаем обгрызенное слово без $mutPos-й буквы
$wordBeginning = mb_substr($wordFrom, 0, $mutPos);
$wordEnding = mb_substr($wordFrom, $mutPos + 1);
// Ищем такие псевдослова
if ($mutPos < self::SUB_DICTIONARIES_MAX) {
// Ура, мы можем воспользоваться соответствующим вспомогательным словарём
$subDictionary = $this->_subDictionaries[$mutPos + 1];
$pseudoWord = $wordBeginning . $wordEnding;
$pseudoWordKey = binary_search($subDictionary, $pseudoWord, 0, NULL, [$this, 'SubDictionaryWordsCmp']);
if ($pseudoWordKey >= 0) {
// В PHP так и не реализовали установку итератора в массиве по ключу,
// поэтому обходим проблему через хранение связанных ключей в словаре
$row = $subDictionary[$pseudoWordKey];
foreach ($row[self::_SDW_WORDS_KEYS] as $key) {
// Не повторяемся - пропускаем ранее использованные слова
if (in_array($key, $excludedWordKeys)) continue;
$variants[$key] = [$key, $mutPos];
}
}
}
else {
// Вспомогательного словаря нет - берём основной, ищем начало слова и перебираем всё подходящее
if ($mutPos == 0) {
// Когда совсем нет вспомогательных словарей, и рассматривается мутация
// первой буквы слова, это совсем не круто - нужно использовать полный перебор
// (здесь тоже можно пойти на оптимизацию группировки слов по длине)
$key = 0;
}
else {
// Определяем с какой позиции в словаре начинать перебор
$key = binary_search($this->_dictionary, $wordBeginning);
if ($key < 0) {
$key = -$key;
}
}
// Перебираем
for ($key; isset($this->_dictionary[$key]); $key++) {
$word = $this->_dictionary[$key];
// Можно выходить, если слово уже начинается не так
if (mb_substr($word, 0, $mutPos) != $wordBeginning) {
break;
}
// Пропускаем по критерию длины слова (простор для дальнейшей оптимизации)
if (mb_strlen($word) != $wordLen) {
continue;
}
// Наконец, проверяем соответствие конца слова
if (mb_substr($word, $mutPos + 1) != $wordEnding) {
continue;
}
// Не повторяемся - пропускаем ранее использованные слова
if (in_array($key, $excludedWordKeys)) continue;
// Слово подходит, добавляем как вариант
$variants[$key] = [$key, $mutPos];
}
}
}
return $variants;
}
3) Работа со словарём
Алгоритм хорошо, но у нас есть источник данных (слов) ввиде файла, с которым надо эффективно и много работать из алгоритма поиска.
Да, этот файл-словарь отсортирован по алфавиту по возрастанию. И он не такой уж гигантский, всего около 1 Мб, так что мы можем его смело загрузить для работы в оперативку целиком.
При этом, конечно, следует понимать, что в «загруженном и разложенном» в структуру данных ввиде массива, в зависимости от языка словарь будет занимать больше памяти. Для PHP 5.4 получилось что словарь в загруженном виде весит около 6 Мб.
Сюда же.
Забегая вперёд, подсловари весят ещё больше.
[Здесь же первая мысль о логичности использования БД. Но решил попробовать сделать сначала без неё.]
Однако:
— в PHP array_search тупой перебиратор, сказать ему «эй, массив же сортирован, ищи бинарно» возможности нет, других подходящих функций из коробки нет, играть костылём flip-keyexists не хотелось да и сложно было применить
— даже если б была функция быстрого бинарного поиска в сортированном массиве, имеется проблема поиска по маске с выбитым символом.
3.1) Быстрый поиск по сортированному массиву первого из неуникальных значений
Первое решается велосипедом бинарного поиска для PHP. Одолжил у товарища покататься,
http://ift.tt/1ktZo4I.
Следует заметить, что эта версия бинарного поиска самая обычная, арифметическая, пригодная для работы в сортированном массиве с последовательной целочисленной нумерацией (ключи от 0 до N-1 например).
Использовал правда не как есть, а модифицировал поиск. В случае массива неуникальных элементов посик останавливался на первом попавшемся равном искомом. А мне нужно было чтоб он отдавал позицию самого первого по ключу из одинаковых элементов массива. Смысл — чтобы можно было упростить последующий алгоритм, и при переборе из набора равных просто следовать от найденного ключа вниз по массиву.
Пример: ищем МУА, есть массив (см. ниже) [… 99-МС(т)ИТЕЛЬ, 100-МУ(з)А, 101-МУ(к)А, 102-МУ(р)А, 103-МУ(т)А, 104-МУ(х)А, 105-МУ(р)АВЕЙ, 106-МУ(р)АВЕЙНИК… ] Обычный бинарный поиск попадает очередной итерацией допустим попадает в ключ 102. Значение элемента (МУА, получилось из слова МУРА) равно искомому (МУА, ищем потомков для МУХА) и этот ключ нам и пришёл бы. И потом загромождай логику перебором и вверх и вниз. Модифицированный алгоритм находит именно самый первый, ключ 100, и далее можно идти последовательно вниз по массиву, пока элемент == искомое.
Модифицированный бинарный поиск
/**
* Двоичный поиск в сортированном массиве
*
* @param array $a - Отсортированный массив (по возрастанию)
* @param mixed $needle - Значение, которое ищем
* @param int $first - Первый индекс массива для поиска (включая)
* @param int $last - Последний индекс массива для поиска (не включая)
* @param string $compare - Функция сравнения. Аналогичного вида как для usort
*
* @return int
* Возвращает индекс в массиве искомого значения.
* Иначе возвращает -(insert_index + 1).
* insert_index является индексом наименьшего элемента массива,
* который больше чем искомое значение, либо равен sizeof($a) если искомое
* больше всех элементов массива.
*/
function binary_search(array $a, $needle, $first = 0, $last = NULL, $compare = 'default_cmp')
{
if ($last === NULL) {
$last = count($a);
}
$lo = $first;
$hi = $last - 1;
while ($lo <= $hi) {
$mid = (int)(($hi - $lo) / 2) + $lo;
$cmp = call_user_func($compare, $a[$mid], $needle);
if ($cmp < 0) {
$lo = $mid + 1;
} elseif ($cmp > 0) {
$hi = $mid - 1;
} else {
$hi = $mid - 1;
// В случае массива с уникальными элементами можно сразу возвращать первый попавшийся индекс $mid
// Но мы проходим всю глубину до конца, чтобы получить бинарно именно самое первое вхождение искомого.
//return $mid;
}
}
$cmp = call_user_func($compare, $a[$lo], $needle);
return $cmp == 0 ? $lo : -($lo + 1);
}
/**
* Стандартная функция сравнения
*
* @param mixed $a - Левое сравниваемое
* @param mixed $b - Правое сравниваемое
* @return int Результат сравнения: -1 меньше, 0 равно, 1 больше
*/
function default_cmp($a, $b) {
return ($a < $b) ? -1 : (($a > $b) ? 1 : 0);
}
3.2) Вспомогательные словари псевдослов
Второе — прикинул что «оперативка вполне выдержит» и решил сделать через подсловари. Где i-й подсловарь построен из основного словаря с вырезанием i-й буквы из слова. Типа МАШИНА => (i=2) МШИНА. По таким подсловарям можно применять тот же бинарный поиск для случаев выбитых букв на позициях, по которым есть подсловари.
В случае когда выбитая буква слишком далеко от начала слова, и подсловаря под такую позицию нет, то поступаем следующим образом:
— в основном словаре ищем «невыбитое начало»
— от найденной позиции простым перебором идём по массиву вниз, пока элемент (слово) начинается как ищем, имеет нужную длину и собираем в варианты все из таких слов, что и оканчиваются как надо.
Поскольку перебор идёт по ограниченной части словаря, где при старте первая позиция определяется бинарным поиском, уже при трёх подсловарях перебор при рассмотрении выбивания 4-й буквы и старше уже не является фатально узким местом.
Приемлемым компромиссом по память/скорость вышло использование 3-4 подсловарей.
Цифры для трансформации «муха»-«слон»:
| Конфигурация |
T загрузки словарей |
T поиска |
T итого |
Потребление ОЗУ |
| Только основной словарь |
0,02 сек |
137 сек |
137 сек |
6 Мб |
| 1 подсловарь |
0,61 сек |
16,40 сек |
17,01 сек |
25 Мб |
| 2 подсловаря |
1,20 сек |
4,73 сек |
5,93 сек |
44 Мб |
| 3 подсловаря |
1,85 сек |
2,72 сек |
4,57 сек |
62 Мб |
| 4 подсловаря |
2,42 сек |
0,82 сек |
3,24 сек |
79 Мб |
| 5 подсловарей |
2,98 сек |
0,77 сек |
3,75 сек |
97 Мб |
Цепочка: «муха» — «мура» — «фура» — «фора» — «кора» — «корн» — «коан» — «клан» — «клон» — «слон» (9 переходов)
Конечно, абсолютно логично что 5-й подсловарь (где из слов убрана 5-я буква и получившееся пересортировано) для превращения 4-буквенных мухи и слона не нужен, и является только обузой. Но посмотрим на другом примере:
Для сравнения, превращение из «сосна» в «белка»:
— для 4 подсловарей: загрузка 2,41 сек, поиск 1,07 сек, итого 3,48 сек
— для 5 подсловарей: загрузка 3,01 сек, поиск 0,36 сек, итого 3,37 сек
Т.е. 5-й подсловарь можно добавлять разве что после оптимизации хранения словарей, кэширования, алгоритма. А сейчас он только лишнее потребление оперативки.
Но… Но «просто как-то сносно работающий вариант на коленке» меня не устроил. И я продолжил совершенствовать превращение мух в слонов.
1-я версия (PHP 5.4)
*
* Здесь хорошо бы сделать паузу для отдыха глаз, чашка кофе, и в этом духе
*
Слону помадой выкрасила ухо,
Второе, хобот, хвостик и теперь
Летает в спальне розовая муха,
Жужжит и бьется головой о дверь.
kekc @hohmodrom.ru
Версия вторая
Причесал многое.
Добавил проверок.
Добавил бросание исключений вместо тихо-непонятного умирания.
Выделил конфиг.
Приготовился к переключению на БД — вынес дата-логику в отдельный маппер.
И т.п. по архитектуре.
Но интересно не это. Самые интересные изменения тут это парсер, фактор случайности и функция оценки, основанная на частотных характеристиках букв.
1) Парсер
Я заметил что исходный словарь хоть и достаточно большой, но там почему-то нет даже некоторых общеупотребительных слов. И внимание ))) там
не было слона!
Слоненок был,
слониха была, а слона упс. Дискриминация.
Да, для выполнения поставленной цели (сделать из мухи слона) для первой версии пришлось погуглить характерные ответы-цепочки, убедиться, к удивлению, что многих слов, опять же, нет в словаре, и добавить штук несколько вручную на соответствующие позиции.
[И да, в этом словаре я наткнулся в первый раз (из последующих шишек php sort, несмотря на верную локаль для setlocale и mb_string) что слова на Ё, внезапно, были в конце словаря.]
Решил исправить этот момент, взяв дополнительные слова пусть и не из готового для тех.использования словаря, но хоть откуда.
Немало ссылок вело на http://ift.tt/1kSnWUD, но он внезапно оказался уже который год предан забвению злым Яндексом, купившим в своё время Народ.ру и сломавшим его в погоне за фертингами.
Но тут помог великий вебархив, за что ему спасибо.
Выкачал всё что было, весь сохранившийся «словарь кросвордиста», сохранил в data/psrc/, написал parse.php на регулярке (которую потом несколько раз поправлял, т.к. сайт был у человека, похоже, на MS Word написан, и странички были не совсем идентичны по вёрстке), — расширил словарь процентов на 50%.
2) Фактор случайности
Цепочка получалась всегда одна и та же, что, в общем, очевидно. Чтобы иметь возможность «игры» и «вдруг найти лучше», ввёл фактор случайности на mt_rand в функцию оценки. Стало получаться интереснее. Иногда действительно стали видны новые, более короткие цепочки, о которых раньше и не догадывался.
Есть конечно и обратная сторона — для неудобных пар бывает поиск и не находит цепочки. Или находит несколько длиннее обычной. Но всё же основной случай достаточно стабилен.
Более конкретно, случайность введена «очень слегка» — в функцию сравнения при упорядочивании по приспособленности нового поколения — слова, имеющие одинаковую оценку приспособленности стали располагаться в случайном порядке.
Элементы рандома
// Сортируем новое поколение по "степени приспособленности" (похожести последнего слова цепочки на искомое)
usort($mutationChains, function($a, $b) {
$diff = $b['score'] - $a['score'];
return $diff ? $diff : mt_rand(-1, 1);
});
3) Функция оценки
Из МУХА СЛОН получался довольно живенько и симпатично, в пределах 10 переходов.
Но (!)
из МУХА слово СЛОГ получалось… упрямо переходов в 60-70 (!).
А ведь очевидно, что должно бы быть всего на 1 длиннее чем в СЛОНа. Человеку очевидно. Машине нет, она по алгоритму. Ошибка алгоритма. Ошибка функции оценки.
Экспирементировал немало, не скрою.
Получалось ну на 5 позиций укоротить цепочку при сомнительных изменениях в разбалловке. Но это же не тот результат который нужен.
Очевидно, с лёту с корректировки проблема не решалась, думал. В чём дело. В чём разница. Разница в последней букве, да, факт. Там слоН, а тут слоГ. Чем же эти буквы так отличаются, что всё так плохо…
Правильно. Частотой употребления! И соответственно числом связанных вариантов мутаций. То есть, «полный хит по Г=Г» может быть хуже, или по крайней мере не намного лучше для оценки «приспособленности», чем «не хит Н, М, К,… != Г». Но, конечно, гораздо лучше чем «не хиты Ы, Ъ, Щ,… != Г».
Взял таблицу частот употребления букв из вики. (На самом деле это не совсем корректно, надо по имеющемуся словарю существительных частоты считать, но вряд ли бы были кардинальные различия). Вбил как есть в код. Это не очень красиво, да, но это пока и пусть. Раскроил частоты букв на нормированные массивы по гласным и по согласным, с нормировкой по максимально употребительной гласной/согласной. Переписал функцию оценки. ЕСТЬ! СЛОН + 1!
Да и сам СЛОН стал получаться ещё на шаг-другой быстрее.
Работа с частотами букв
При инициализации:
public function __construct()
{
//$this->_mprDictionary = null;
$this->_mprDictionary = new DictionaryFileMapper();
$this->_vovels = "аоуыэяёюие";
$this->LoadLetterFrequencies();
}
private function LoadLetterFrequencies()
{
$this->_lettersFrequences = [
'о' => 0.10983,
'е' => 0.08483,
'а' => 0.07998,
'и' => 0.07367,
'н' => 0.06700,
'т' => 0.06318,
'с' => 0.05473,
'р' => 0.04746,
'в' => 0.04533,
'л' => 0.04343,
'к' => 0.03486,
'м' => 0.03203,
'д' => 0.02977,
'п' => 0.02804,
'у' => 0.02615,
'я' => 0.02001,
'ы' => 0.01898,
'ь' => 0.01735,
'г' => 0.01687,
'з' => 0.01641,
'б' => 0.01592,
'ч' => 0.01450,
'й' => 0.01208,
'х' => 0.00966,
'ж' => 0.00940,
'ш' => 0.00718,
'ю' => 0.00639,
'ц' => 0.00486,
'щ' => 0.00361,
'э' => 0.00331,
'ф' => 0.00267,
'ъ' => 0.00037,
'ё' => 0.00013,
];
// Раскладываем общую таблицу на подтаблицы гласных и согласных
$this->_lettersFrequencesVovel = [];
$this->_lettersFrequencesConsonant = [];
foreach ($this->_lettersFrequences as $letter => $frequency) {
if ($this->IsVovel($letter)) {
$this->_lettersFrequencesVovel[$letter] = $frequency;
}
else {
$this->_lettersFrequencesConsonant[$letter] = $frequency;
}
}
// Нормируем.
// Массивы частот упорядочены, потому поиск не требуется
$maxFrequency = reset($this->_lettersFrequencesVovel);
foreach ($this->_lettersFrequencesVovel as $letter => &$frequency) {
$frequency /= $maxFrequency;
}
$maxFrequency = reset($this->_lettersFrequencesConsonant);
foreach ($this->_lettersFrequencesConsonant as $letter => &$frequency) {
$frequency /= $maxFrequency;
}
}
/**
* Является ли буква гласной
*
* @param string $letter - Буква
* @return bool
*/
public function IsVovel($letter)
{
return false === mb_strpos($this->_vovels, $letter) ? false : true;
}
Функция оценки:
/**
* Функция оценки похожести слова
*
* @param string $word - Оцениваемое слово
* @param string $comparationWord - Эталонное слово
* @return int
*/
public function GetWordScore($word, $comparationWord)
{
// Частый случай поиска - с одним и тем же эталонным словом, - используем кэширование
static $cachedComparationWord = '';
static $wordLen = 0;
static $cwLetters = [];
if ($cachedComparationWord != $comparationWord) {
$cachedComparationWord = $comparationWord;
$wordLen = mb_strlen($comparationWord);
$cwLetters = [];
for ($i = 0; $i < $wordLen; $i++) {
$letter = mb_substr($comparationWord, $i, 1);
$cwLetters[$i] = [
'letter' => $letter,
'isVovel' => false === mb_strpos($this->_vovels, $letter) ? false : true,
];
}
}
$score = 0;
for ($i = 0; $i < $wordLen; $i++) {
$letter = mb_substr($word, $i, 1);
$isVovel = $this->IsVovel($letter);
// Полностью совпадающим символам максимальная оценка = 3
if ($letter == $cwLetters[$i]['letter']) {
$score += 1;
if ($isVovel) {
$score += 2 + 1 * $this->_lettersFrequencesVovel[$letter];
}
else {
$score += 0 + 3 * $this->_lettersFrequencesConsonant[$letter];
}
continue;
}
if ($isVovel) {
if ($cwLetters[$i]['isVovel']) {
// Совпадение позиции гласной буквы = 2
$score += 2 + 2 * $this->_lettersFrequencesVovel[$letter];
}
else {
// Наличие гласной буквы = 1
$score += 2 * $this->_lettersFrequencesVovel[$letter];
}
}
else {
if (isset($this->_lettersFrequencesConsonant[$letter])) {
$score += 3 * $this->_lettersFrequencesConsonant[$letter];
}
}
}
return round($score);
}
Новые цифры для трансформации «муха»-«слон»:
| Конфигурация |
T загрузки словарей |
T поиска |
T итого |
Потребление ОЗУ |
| Только основной словарь |
0,04 сек |
210 сек |
210 сек |
9 Мб |
| 1 подсловарь |
0,98 сек |
26,16 сек |
27,14 сек |
42 Мб |
| 2 подсловаря |
1,97 сек |
9,97 сек |
11,94 сек |
72 Мб |
| 3 подсловаря |
2,98 сек |
4,72 сек |
7,70 сек |
102 Мб |
| 4 подсловаря |
3,97 сек |
1,37 сек |
5,34 сек |
130 Мб |
| 5 подсловарей |
4,96 сек |
1,30 сек |
6,26 сек |
158 Мб |
Цепочка: «муха» — «муна» — «мина» — «лина» — «линн» — «лион» — «сион» — «слон» (7 переходов).
Как видим, потяжелел словарь (с 0,68 Мб до 1,03 Мб, +51%), а с ним подсловари и итоговый жор оперативки. Комбинаторика улучшилась, и хоть и на каждом шаге мутаций стало рассыпаться больше, а значит шагать стали медленнее, — конечная цель, при достижимости, стала получаться по результату быстрее, за меньшее число шагов.
Однако, по времени поиск получился совсем не быстрее, даже для 4 подсловарей. Один фактор другой не компенсировал. Тем не менее, по сути расширить словарь абсолютно корректный и необходимый ход для приближения к реальным боевым условиям. И есть ещё множество справочников кроссвордиста и словарей, в том числе онлайновых, с которыми можно поработать для расширения нашего словаря.
2-я версия (тот же PHP 5.4).
*
* Вообще, эта задача кажется бесконечной.
* И в этой долгой дороге к совершенству,
* Пожалуй, на этом пятачке стоит сделать ещё один перекур.
*
Некий деятель науки
ДЕЛАТЬ стал СЛОНА из МУХИ:
Надувал, надувал,
Поглядеть народ позвал.
Удивить он всех хотел…
Ну а слон-то улетел!
Версия третья
Честно признаться, ожидал от версии большего. Всё-таки база (была под рукой MySQL 5.5) должна, ну должна же была обеспечить взлёт хотя бы в разы, если не на порядки.
1) База и скорость?
Судя по всему, в версии с файлами я фактически добился эффекта memcache — куча словарей в памяти, а алгоритм, в общем, един и для файл- и для mysql-версий. В построении базы вроде соображаю, все нужные индексы для работы были проставлены.
Сами файлы меня тормозили только на этапе их загрузки в оперативку — порядка 4 сек. А поиск из мухи слона происходил порядка 0,8 сек. Так что в общем зачёте на доступность побеждает версия MySQL, с «загрузкой» порядка 0,002 сек и поиском порядка 0.95 сек. Понятное дело, загружать ей ничего не требуется, после одного-двух прошлых обращений скрипта, кэш прогрет и всё уже загружено и ждёт.
Структура базы
--
-- База данных: `metagram`
--
-- --------------------------------------------------------
--
-- Структура таблицы `dictionary`
--
CREATE TABLE IF NOT EXISTS `dictionary` (
`id` int(11) NOT NULL AUTO_INCREMENT,
`name` varchar(255) NOT NULL,
`lang` varchar(30) NOT NULL,
PRIMARY KEY (`id`),
UNIQUE KEY `name` (`name`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8 AUTO_INCREMENT=1 ;
-- --------------------------------------------------------
--
-- Структура таблицы `word`
--
CREATE TABLE IF NOT EXISTS `word` (
`id` int(11) NOT NULL AUTO_INCREMENT,
`value` varchar(50) NOT NULL,
`description` varchar(255) DEFAULT NULL,
`dictionary_id` int(11) NOT NULL,
`length` smallint(6) NOT NULL,
PRIMARY KEY (`id`),
UNIQUE KEY `value` (`value`),
KEY `dictionary_id` (`dictionary_id`),
KEY `lenght` (`length`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8 AUTO_INCREMENT=1 ;
-- --------------------------------------------------------
--
-- Структура таблицы `word_pseudo`
--
CREATE TABLE IF NOT EXISTS `word_pseudo` (
`id` int(11) NOT NULL AUTO_INCREMENT,
`value` varchar(50) NOT NULL,
`word_id` int(11) NOT NULL,
`deleted_symbol_pos` smallint(6) NOT NULL,
PRIMARY KEY (`id`),
UNIQUE KEY `value_word_id` (`deleted_symbol_pos`,`value`,`word_id`),
KEY `word_id` (`word_id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8 AUTO_INCREMENT= 1 ;
Так или иначе, ответ за 1 сек лучше чем за 5 сек.
2) Кэширование очевидного узкого места
Изначально, правда, было под 2 сек, из-за обильных запросов SELECT слово ПО ид. Агрессивное кэширование в MySQL-маппере устранило эту проблему. Тоже конечно не оптимальным образом, но и это ещё далеко не хайлоад продакшн, а эксперимент. Вполне терпимо на данном этапе.
Где то в классе DictionaryMysqlMapper
...
private $_cachedWords;
private $_cachedWordKeys;
...
/**
* Получить слово из словаря по указанному ключу
*
* @param string $key Ключ (идентификатор) слова
* @return string|false|null
*/
public function GetWord($key)
{
if (isset($this->_cachedWords[$key])) {
return $this->_cachedWords[$key];
}
$wordRow = $this->_db->FetchOne("SELECT * FROM `word` WHERE `id` = " . $this->_db->QuoteValue($key));
$this->_cachedWords[$key] = $wordRow['value'];
return $wordRow['value'];
}
3) Тюнинг размера популяции
И кстати, в результате отлично себя показавшей функции оценки с учётом частот букв, удалось снизить число популяции в поколении со 100 до 50 без ущерба для результата. К слову, даже популяция в 20 показала себя не намного хуже, но оставил 50.
Это позволило заметно снизить время поиска. На примере тех же мухи и слона с примерно 1 сек до 0,5-0,6 секунд.
Итак,
3-я версия (Вновь PHP 5.4, но уже с MySQL 5.5)
*
* Тут уже и сама статья, по поднятой задачке и объёму, стала «из мухи слоном» )
* Пора подводить итоги.
*
Вышел слон на лесную дорожку,
Наступил муравью на ножку
И вежливо
Очень
Сказал муравью:
— Можешь и ты
наступить на мою!
(с) Рината Муха, «Вежливый слон»
Итоги
На третьем шаге мы имеем решение задачи на PHP 5.4 + MySQL 5.5, требующее порядка 0,5 сек. на превращение мухи в слона за 9 итераций:
'from' => "муха"
'to' => "слон"
'runMode' => "MySQL"
'list' ...
'0' => "муха"
'1' => "маха"
'2' => "мана"
'3' => "манн"
'4' => "ланн"
'5' => "линн"
'6' => "лион"
'7' => "сион"
'8' => "слон"
'timeLoad' => "Инициализация, загрузка словарей: 0,008000 сек."
'time' => "Поиск перехода между словами: 0,551032 сек."
'status' => "готово."
Скрипт при этом не потребляет так конски оперативку, как в версии с чисто PHP и файлами словарей (под 100 Мб), потребление самое обычное. Те же данные, хранящиеся в СУБД, ведут себя более пристойно по аппетитам к памяти.
Что дальше?
Безусловно, решение не идеально, я знаю. Многое ещё можно сделать:
- Вместо одного процесса поиска от начального к искомому, сделать агоритм на двух параллельных процессах поиска: от начального к искомому и от искомого к начальному, с выходом и построением цепочки по первой коллизии пары слов из двух процессов. Насколько я знаю алгоритмы заливки, таклй ход помогает улучшить скорость получения результата в 2-4 раза. Да, генетический алгоритм другой случай, но есть ощущение что вот такое встречное движение и тут даст результат.
- Сделать горизонтальное масштабирование словаря? Раскидать слова разной длины по разным подтаблицам. Для этой задачи это допустимый ход. Ввиде дополнительного поля длины слова и индекса по нему пробовал, — ничего. Значит только партиционирование. Будет ли от этого толк, впрочем, пока затрудняюсь сказать.
- Redis? Memcached?
- Распараллеливание процессов обсчёта поколений генетических мутаций до N штук параллельных процессов, в зависимости от числа ядер на сервере
- Добавить юзер френдли? В цепочках попадаются такие слова, о которых и не слыхивал. Интересно бы в цепочке на клиенте показывать и значение этих слов.
- CP1251? Utf-8 это безусловно прекрасно. Но если работать заведомо только с русскими словарями, или же в сущности словаря указывать кодировку, в которой на самом деле хранятся слова, то почему бы и нет. Строгий 1 байт сильно упрощает работу со строкой для железок, и в 2 раза меньше будет кушать памяти. Это явно неплохо.
- JavaScript версия? В случае массового количества запросов, например хабраэффекта, это неплохая идея — зачем сервер такими вычислениями нагружать, пусть железо на клиенте пыль стряхнёт, кулеры погоняет.
- Серверная версия на C++?
- И наверняка другие ходы, которые пока ещё не приходили в голову.
Тема затягивающая… Может быть, у истории будет продолжение. Во всяком случае, меня зацепило сильно, не меньше чем
Diamond-Square.
PS:
Конечно, в этой статье нельзя не оставить ссылку на то, как делают из мухи слона художники.
Комментарии и замечания приветствуются! Может упустил какие-то простые и важные вещи. Благодарю за внимание.
This entry passed through the Full-Text RSS service - if this is your content and you're reading it on someone else's site, please read the FAQ at http://ift.tt/jcXqJW.
