13.11.2015 14:42
FlameStorm 17 18400 Источник
Многим известна такая старая добрая игра со словами, сделать из мухи слона. Суть её в том, что нужно из начального слова сделать конечное, на каждом шаге меняя только одну букву, получая при этом на каждом шаге осмысленное существительное.

Известный автор книг по занимательной математике Е. Я. Гик в своей книге "Занимательные математические игры" опубликовал такое 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. Одолжил у товарища покататься, terenceyim.wordpress.com/2011/02/01/all-purpose-binary-search-in-php.

Следует заметить, что эта версия бинарного поиска самая обычная, арифметическая, пригодная для работы в сортированном массиве с последовательной целочисленной нумерацией (ключи от 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) что слова на Ё, внезапно, были в конце словаря.]

Решил исправить этот момент, взяв дополнительные слова пусть и не из готового для тех.использования словаря, но хоть откуда.
Немало ссылок вело на chyjik.narod.ru/index.htm, но он внезапно оказался уже который год предан забвению злым Яндексом, купившим в своё время Народ.ру и сломавшим его в погоне за фертингами.

Но тут помог великий вебархив, за что ему спасибо.

Выкачал всё что было, весь сохранившийся «словарь кросвордиста», сохранил в 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:
Конечно, в этой статье нельзя не оставить ссылку на то, как делают из мухи слона художники.

Комментарии и замечания приветствуются! Может упустил какие-то простые и важные вещи. Благодарю за внимание.

Комментарии (17)


  1. buriy
    13.11.2015 18:57
    #8653755
    +12

    Не вижу нигде упоминания алгоритма А* ( https://ru.wikipedia.org/wiki/Алгоритм_поиска_A* ) или хотя бы обычного поиска в ширину ( https://ru.wikipedia.org/wiki/Поиск_в_ширину ).
    Что, подход «сперва учись, потом думай, потом делай» уже не в моде?
    Посмотрите на картинки вот тут: http://buildnewgames.com/astar/, должно помочь!


    1. xenohunter
      13.11.2015 19:29
      #8653795
      +5

      Мне кажется, что не хуже и другой подход: «сперва думай, потом делай, затем учись, потом снова думай, и, наконец, делай превосходно». Пытаться реализовать что-то самому, не изучая детально готовые решения — очень полезно, на мой взгляд.

      UPD: Однако, за ссылки спасибо.


      1. kefirfromperm
        16.11.2015 08:32
        #8655231
        +1

        25 лет
        «Программист. Музыкант. Геймер. Гик.»

        Стыдно не знать основ теории графов.


        1. xenohunter
          16.11.2015 11:57
          #8655377

          Согласен, стыдно. Вот я и учусь, а вовсе не говорю, что их знать не нужно.


    1. 0leGG
      14.11.2015 04:49
      #8654129

      A* бы тут плохо сработал, кстати, потому что эвристика на такой задаче может в тупик завести очень легко.


      1. buriy
        14.11.2015 11:00
        #8654189

        Вполне возможно, поэтому я бы и ожидал в топике с таким названием сравнения этих двух алгоритмов для данной задачи.


  1. ewgRa
    13.11.2015 19:02
    #8653757
    +2

    Навскидку: каждому существительному из словаря сопоставляем id.

    Делаем карту переходов, возможных между id.

    Таким образом отбрасываем необходимость работы со строками, остаемся наедине с цифрами, задача переводится немного в другую плоскость.

    Дальше напрашивается построение графа и поиск пути между вершинами, ну или деревья. Я думаю с числовыми значениями алгоритм проще будет найти.


    1. FlameStorm
      13.11.2015 22:08
      #8653899

      Хм. В третьей версии фактически так и есть.

      Карта переходов — один из индексов в базе в таблице псевдослов — UNIQUE KEY `value_word_id` (`deleted_symbol_pos`,`value`,`word_id`). Его использование — в селекте MySQL маппера, вытаскивающего мутации из базы.

      кусок кода сборки запроса
      	// Выбираем все подходящие псевдослова из базы
	$query = "SELECT wp.`word_id`, wp.`deleted_symbol_pos`, wp.`id`, wp.`value`, w.`value` AS `word`"
		. " FROM `word_pseudo` AS wp"
		. " JOIN `word` AS w ON (w.`id` = wp.`word_id`)"
		. " WHERE w.`dictionary_id` = " . $this->_db->QuoteValue($this->_dictionary['id'])
			. " AND w.length = " . $this->_db->QuoteValue($wordLen)
			. " AND wp.`deleted_symbol_pos` = " . $this->_db->QuoteValue($mutPos)
			. " AND wp.`value` = " . $this->_db->QuoteValue($pseudoWord)
			. (
				empty($excludedWordKeys) ? "" : 
				" AND wp.`word_id` NOT IN (" 
				. implode(',', array_map(function($key) {
					return $this->_db->QuoteValue($key);
				}, $excludedWordKeys))
				. ")"
			)
		. " ORDER BY wp.`word_id`"
	;


  1. Scf
    13.11.2015 20:05
    #8653819
    +5

    Ну да, очередной пример полезности теории графов. Эта задача сводится к поиску кратчайшего пути в графе. Если хранить граф в матричном виде, то получаем для 10к слов 10к * 10к бит = 12 мегабайт. С учетом неориентированности графа, память можно уполовинить до 6 мегабайт.


    1. FlameStorm
      13.11.2015 22:41
      #8653933
      +3

      Да, спасибо, то был ложный испуг масштабов вот тут:

      Даже если дать очень оптимистичную оценку на среднее число вариантов модификаций в 5 (всего!), то если к какому-то слову минимальный путь составит 10 шагов, то в памяти должно уместиться дерево в 510 ~= 10 млн нодов

      Моя ошибка.

      Ведь мы будем строить дерево из уникальных элементов (слов), а словарь-то не такой огромный, совсем не 10 млн слов, а на порядки меньше. А точнее, в нашем случае, 64765 слов.

      Причём, распределение по длинам следующее:
      распределение
      COUNT(*) 	length 	
111	2
956	3
3477	4
7224	5
8517	6
9356	7
8328	8
7540	9
5290	10
4315	11
2835	12
2346	13
1680	14
971	15
691	16
361	17
228	18
117	19
58	20
25	21
14	22
3	23
1	24


      1. b_oberon
        15.11.2015 15:14
        #8654897

        А для полного счастья вместо реляционной базы данных можно использовать граф-ориентированную, например neo4j или OrientDB.


  1. phikus
    13.11.2015 21:14
    #8653861
    +2

    Лина? Линн? Сион?
    Ты вместо словаря существительных словарь имён собственных что ли раскурил?


    1. FlameStorm
      13.11.2015 22:55
      #8653941

      Выше я оставлял ссылку, откуда втянул в словарь дополнительные слова — из одного из словарей кроссвордистов. А у кроссвордистов география и имена в ходу. Да, хорошо бы без них, но пока лучших словарей не обнаружил. Во всяком случае, в этих хоть нет глаголов, прилагательных и подобного.

      Замечание уместное.

      Разве что Сион — это ещё и «Вид православной церковной утвари, хранилище просфор (освященного хлеба)», а Линн — «Замок в Эстонии».


  1. bitec
    13.11.2015 21:23
    #8653869
    +5

    Генетический алгоритм?? Зачем так сложно?? Ээээ, это задача WordLadder на leetcode со средней сложностью, обычный обход дерева в ширину! Причем решение мегаэлегантное, даже граф строить не надо, для коротких слов можно последовательно менять каждую букву и проверять на наличие в словаре — таким образом получим «ребро», которое кладем в очередь.


    1. FlameStorm
      13.11.2015 22:47
      #8653935

      Спасибо за совет! Я уже разобрался, что масштабы были не столь эпичны.

      Но как тренировочное применение генетических алгоритмов вполне можно оставить.
      Предложенное элегантное решение и мне и читателю на заметку.


  1. Valle
    14.11.2015 06:33
    #8654141
    +1

    Я тут быстренько попробовал на первом попавшемся словаре и из мухи в слона обычным BFS прихожу за 25 миллисекунд. Словарь далеко не 6 мегабайт, но этот поиск наверное займет резонное время и место даже на большом словаре.

    муха-мура-мара-кара-каре-кафе-кафр-каир-каин-клин-клон-слон
            long start = System.currentTimeMillis();
        String[] dict = "кафр урюк быть весь этот мочь один себя свое если рука даже свой дело есть глаз день надо идти друг тоже лицо ведь жить нога пока хотя сила вода куда стол ночь отец дать твой лишь свет жена окно мать утро душа таки чуть хоть уйти пять путь пора тело язык мама небо брат туда мало труд сюда чтоб тихо двор иной угол губа снег либо дядя мера край река рота речь гора едва море врач ясно боль вещь цель план пара след пить мимо враг удар мало вниз двое счет игра член хлеб банк идея союз метр вера бить звук роль петь поэт лист выше этаж дочь опыт рост кожа баба дама поле ящик цена зато тень лето воля цвет круг факт стул вино ради танк зима знак семь мозг рыба щека папа срок курс куст явно чудо тема крик ключ конь штаб пора трое ужас ссср очко пыль боец черт царь даль слух клуб беда обед тетя лечь смех злой мост пуля мясо долг рада пиво зона вход итак пост дача рано ниже кино горе вряд суть стен толк вкус полк кофе база урок труп муха лапа плащ нету шкаф сеть грех парк борт луна волк пила файл куча пояс гриб слой изба юный пища храм рана холм доля воин тьма итог боже гном цепь ужин баня жест щель узел гроб шанс порт июнь март перо яйцо туча верх нерв этап заяц дума роза кадр июль фонд ныне виза груз ярко внук стук печь мина хрен соль руль мука штат течь блок дура каша кафе лифт трус мода сено поза брак плод окоп сидя вина сбор флот мыло стоя гнев плюс змея один уход звон нквд пляж слон дыра бред риск взор лужа орел нары юбка рожа дата стыд ноль юмор учет вица флаг грек марш вена диск теща алый удав сего лыжа плач цирк бюро село мышь шуба роса упор рама указ кран хата поди сухо нуль дуть очаг шлем буря мрак матч коза темп гром холл веко тьфу стон сорт заря сейф визг млрд семя осел пруд офис гусь доза стоп елка змей тоня орех туго пена живо кпсс сало коса толь мыть ранг негр ритм стая блин азия тигр икра худо овца фара вяло плот клок купе сани кура даба чушь овощ цикл язва ныть лорд плат нить чаша эфир мощь уста секс скот винт жечь яхта литр роща крым нота лихо жанр лежа лить леди киев шрам вред нева ниша нрав миля яков трон лень зять выть игла дина троп дитя пень дико шнур кора уток штык укол прут мент тост джип крюк бокс толя прах лось свод фига клещ мазь ядро корм русь залп клей клад жара иуда граф сука бинт хаос плен тупо мгла жопа грош батя эльф няня кода такт ваза чара урал фаза дуга мочь пуща ложе этак пина безо дева псих фунт дуло клан паук трап рыло град нора ожог спор рака вить джин жать шить араб липа тасс гага рыть тяга близ чадо клоп арка чаек обои клык нато фото клюв бунт трос отек сема меню вата жила мисс кара урод эдак ляля крем утюг мило рига езда усик узор кнут босс приз медь тушь перс моча марс косо пакт сень мари орда веня борщ алло шелк чаща веер раса шарф враз торт кайф моща тура выпь уйма ноша гарь пики лада маяк долл стих карп майя вонь крах серо лига зубр плац урна нива горб зола взад иней мсье депо хрип бомж шина дурь руда джаз герб мара дорн соус кедр пузо хвоя рейд сеул стаж жаба морг урка клин опор шест заем сени кабы харя йога трюм чека саше ушко гимн ямка хлам стан дань ладо вилы трюк зной паек блик рема слог тина квас жгут муть шаль пред сайт пята дьяк клен сечь швед лунь лязг гувд обоз вмиг пони балл щука степ жало корж укор ввод дичь утес скат воск сера щелк гиря жрец сова ежик шейк гута ирак юнец раба огпу бюст шило филя бора кейс серп пани вбок писк укус дыня вишь срыв идол лира пари сыпь нона ряса гной экий харч овес лиса фрак ушиб крот мура фрау мэтр лавр стог шифр гипс оный подо баян краб оспа муза цент бишь зуда наст убор кипр кпрф рута сушь жлоб зонт тест сажа гриф бант сбой авто итар атом гуща храп амур деть байт моль эсер чума загс дыба лава спец ковш торг улей сода рейх иран падь лоно раис мэри бусы кило чело жижа фойе киль рысь ново герр омут сбыт бита лата факс омон ария мена жуть ларь стык грач дуэт ярус вдох сыро срез плуг вьюк сноп пуск люкс соло шурф тайм тара удел буги агат спой флер сруб явка цинк ринг мель омар ясли срам сити круп фуга спид умно кров печь уезд спад паче марь горн этюд гнет роба ярый глум тишь улов куда жюри брод боек софа мять кндр ялта лупа елей чили плюс юрта зонд репа прок чета хост трлн грим брус ирма фила плед сито арап кипа пирс треп кума цска стер тент лыко гать лоза путч доха куль жезл ухаб диво вага иглу чача гель нате глас сгиб суша айда корт пляс свая веха дюна опус клич корн понт яуза амир сток болт паря тута хлев фарш свищ кина ишак арат синь тула торс альт трах сыта бейт тора рябь пеня эфес алан бола арба прыщ блат топь угон кляп съем увар хлоп наин оное фура сход ласт высь дора пюре вошь выть шлюз путы жары рать ахти эмир скоп баул цаца дуля шутя пике эссе енот упад скит сыск финн лжец шлак межа вона мяло хорь дюйм бард овал азот барк фора узда угар тога форт снос перл уран мхат олин юнга трак вояж убег меря резь поем овин аист соха ткач дерн наем жбан злак сват каир обух каюк урон панк плес плов гран ящер нома вымя ринк лама рожь табу зуев нега ромб плющ морж едок янки изюм кома желе шлаг обет нимб баск гурд киса кепи любя усть ввоз ролл буде слет джем фарс щепа золь бега тире олух отит клев ласа ложа аозт сума куща каюр слых гкчп шейх блюз идиш бриз копа бяка фанк лдпр мана навь пядь каин тятя клеш рейн шмон тлен кофр блеф быль лаос люто шлях барс бура сырт сеид весь арык норд аура увал гонг хина озон скак плав убой чита лоск арфа ширь кока кета сноб вето вест омск кача вязь мавр адан крит берн едко сома рань слив скок фант темя ярок стек течь гнус морс смак трио охра мета тета сляб морт скуп гурт хром овен тата мзда узко корь соты зело серб зыбь сонм бель улан гост ворс пенс кипу иена обод фифа торф юрин титр финт зева ушат хрящ клон харт опий деев тюря кунг понг стяг алоэ бэби зоря тать кряж сказ сена дюже лгун туша мкад пума змий слом олим джей ажур крат усач купа паяц каре дзот копь блиц эпос гиви аоот ковы сван форс гунн лань мята скиф шпик жмот пасс натр хаус маки софт шарм плут рувд лука гоби немо пшик сыто фарт биль маго сага неуч лафа кали пион буян галл бета эвон голо челн крой риза саго беня опал фиат апис лото тпру лясы хаки вить имам ярмо жито спас анри крен вьюн хота фикс сбег юшка гарт чтец темь глот овод таец куга вира новь кото коми анус леер аман щорс рагу драп хрыч блуд хлыщ краз чаво жмых швея виль руза вега вече".split(" ");
        HashMap<String, Integer> dictSet = new HashMap<>(dict.length);
        for (int i = 0; i < dict.length; i++) {
            dictSet.put(dict[i], i);
        }
        int[][] graph = new int[dict.length][];
        for (int i = 0; i < dict.length; i++) {
            char[] word = dict[i].toCharArray();
            ArrayList<Integer> adj = new ArrayList<>();
            for (int j = 0; j < word.length; j++) {
                char existingChar = word[j];
                for (char ch = 'а'; ch <= 'я'; ch++) {
                    if (ch != existingChar) {
                        word[j] = ch;
                        Integer wordId = dictSet.get(new String(word));
                        if (wordId != null) {
                            adj.add(wordId);
                        }
                    }
                }
                word[j] = existingChar;
            }
            int[] adjArray = new int[adj.size()];
            for (int j = 0; j < adjArray.length; j++) {
                adjArray[j] = adj.get(j);
            }
            graph[i] = adjArray;
        }
        LinkedList<Integer> queue = new LinkedList<>();
        int fromId = dictSet.get("слон");

  1. gromozeka1980
    14.11.2015 18:58
    #8654433

    добавил в качестве перехода появление новой буквы в произвольном месте слова
    цепочка с максимальным приростом:

    еж -> уж -> буж -> бук -> бок -> блок -> блик -> бзик -> узик -> узник -> ушник -> пушник -> путник -> путаник -> путание -> питание -> писание -> списание -> спивание -> спаивание -> опаивание -> опаливание -> осаливание -> оскаливание -> оскабливание -> поскабливание -> проскабливанное

    ну и да, ничего сложнее BFS тут не нужно, конечно