Как сделать из мухи слона
Суть её в том, что нужно из начального слова сделать конечное, на каждом шаге меняя только одну букву, получая при этом на каждом шаге осмысленное существительное.
Классическое решение задачи как из мухи сделать слона
Как из мухи сделать слона из 16 ходов
муха — мура — тура — тара — кара — каре — кафе — кафр — каюр — каюк — крюк — урюк — урок — срок — сток — стон — слон.
Решение из 10 ходов (10 переходов):
муха — мура — фура — фора — кора — корн — коан — клан — клон — слон
Решение из 9 ходов (9 переходов):
муха — маха — мана — манн — ланн — линн — лион — сион — слон
Самый короткий вариант из 8 ходов:
муха — муна — луна — лина — линн — лион — сион — слон
муха — муна — мина — лина — линн — лион — сион — слон
Значение словосочетания «делать из мухи слона»
Делать из мухи слона
— сильно преувеличивать что-либо, придавать чему-либо незначительному большое значение
— крайне преувеличивать, представлять мелочь и ничтожное имеющим крупное значение
Предложения со словосочетанием «делать из мухи слона»
Вполне вероятно, её мать преувеличила серьёзность проблемы с деньгами, она всегда делала из мухи слона. А что, если в этот раз всё действительно серьёзно?
Триш Мори, Все очень просто, 2013
Внешне он — само спокойствие, а потому и все вокруг недоумевают, отчего у него постоянно возникают стычки с трагиками, делающими из мухи слона.
Лууле Виилма, Лууле Виилма. Книга-надежда, книга-спасение! Исцеление от любой болезни силой Любви, 2015
— С работы я вернулся вовремя, — нахмурился отец, — Что ты, детуня, делаешь из мухи слона?
Анатолий Зарецкий, Мысли из палаты №6
Мне казалось, что перепуганные, затравленные «буржуи» боятся даже собственной тени и делают из мухи слона.
И. В. Одоевцева, На берегах Невы
— Ну вот, ты опять делаешь из мухи слона.
Меллори Кейн, Третье чудо, 2015
И вы совершенно напрасно делаете из мухи слона.
Элизабет Мид-Смит, Семь молоденьких девиц, или Дом вверх дном, 1904
Не делай из мухи слона. Вдруг полетит.
В. Н. Ковалев, Афоризмы-размышлизмы
Перестаньте же делать из мухи слона!
Е. А. Тарасов, Как преодолеть свои страхи и комплексы. 10 тестов + 14 правил, 2015
Это всё равно, что делать из мухи слона.
В. В. Козлов, Конфликт: участвовать или создавать…
Ошо, почему я делаю из мухи слона?
Б. Ш. Раджниш (Ошо), Древняя музыка в соснах: в дзен разум внезапно останавливается
Поэтому продолжает делать из мух слонов.
Б. Ш. Раджниш (Ошо), Древняя музыка в соснах: в дзен разум внезапно останавливается
— Может, это и в самом деле чей-то глупый розыгрыш, а я делаю из мухи слона.
Вера и Марина Воробей, В паутине страха
Она не делала из мухи слона, а просто писала.
Джулия Кэмерон, Право писать. Приглашение и приобщение к писательской жизни, 1998
— Всё-таки не понимаю, почему ты делаешь из мухи слона.
Стефани Лоуренс, Безупречная жена, 1997
Принимать малейшую критику, как величайшее оскорбление и делать из мухи слона.
Ирина Бйорно, Тридцать три несчастья, или Как стать ЭНЖеком
Может, я просто все преувеличиваю и делаю из мухи слона.
Алена Бородина, Всё в моих руках, 2013
Крапивница, как правило, имеет отношение к мелким, сокрытым в глубине души страхам, а также к склонности делать из мухи слона.
М. Л. Шульц, Всё будет хорошо!, 2013
Кто выискивает в слове недобрый скрытый смысл, тот его находит, даже если собеседник говорил без задней мысли. Уши слушающего делают из мухи слона.
Лууле Виилма, Тепло надежды, 2012
Если вы не будете делать из мухи слона, то вскоре всё вернётся на круги своя.
Анн Бакюс, Гид по воспитанию детей от 1 до 3 лет. Практическое руководство от французского психолога, 2012
Но дипломаты не были бы дипломатами, если бы не считали долгом своей чести усложнять простые вещи, делать из мухи слона и затягивать решение любого важного
вопроса всяческими искусными способами.
Стефан Цвейг, Мария Антуанетта, 1932
Неточные совпадения со словосочетанием «делать из мухи слона»
И вот по своему обыкновению из мухи делать слона, а потом спекулировать фальшивой слоновой костью, они и раздули один год до юбилея.
В. С. Бушин, Пятая колонна. Отпор клеветникам, 2014
Это значит из мухи делать слона, а из слона муху.
Валентин Мордасов, Святые отцы об исповеди. Духовник и отношение к нему, 1992
Повторяю, вы всё время из мухи делаете слона.
Элизабет Мид-Смит, Семь молоденьких девиц, или Дом вверх дном, 1904
— Это верный признак того, что кто-то склонен из мухи делать слона.
Эдуард Веркин, Большая книга летних приключений, 2009
До сих пор люди умели из мухи делать слона, а вы хотите из мухи сделать человека.
А. Р. Беляев, Ариэль, 2016
Наш смиренник распускает хвост, словно павлин, задирает хохол, а тем временем бесстыжий льстец приравнивает этого ничтожного человека к богам, выставляет его образцом всех доблестей, до которых тому, как до звезды небесной, далеко, наряжает ворону в павлиньи перья, старается выбелить эфиопа и из мухи делает слона.
Эразм (Дезидерий) Роттердамский, Похвала глупости, 1509
Наверняка она опять раздула из мухи слона!
Триш Мори, Все очень просто, 2013
Ещё он сказал, что все дети дерутся время от времени и нечего раздувать из мухи слона.
М. Е. Некрасова, Скелеты на пороге, 2008
Раздуть из мухи слона — и муха лопнет!
Н. Г. Еремич, Тайм-менеджмент для женщин. Как все успевать, 2008
Вдруг раздуваю из мухи слона?
Ю. М. Герт, Избранное, 2014
— Мне следовало бы пойти за женой и успокоить её, а то она способна сделать из мухи слона.
В. И. Крыжановская-Рочестер, Заколдованный замок, 1898
Тоже мне, сделал из мухи слона.
Александр Базель, Пепел страниц
Я подумал, что, может, телевидение, как всегда, раздуло из мухи слона и решило накормить своих почитателей вкусной побасёнкой?
Арчибальд Брукс, Когда зомби оживают… Призрачная магия Черного континента, 2008
Длинные языки раздуют из мухи слона, ведь всем известно, что обычно он не прилагает столько усилий.
Мэдлин Хантер, Опасность в бриллиантах, 2012
Не стоит раздувать из мухи слона.
Ольга Морозова, Ван Гог и Марго (сборник), 2013
Могло ли быть так, что она раздула из мухи слона?
Морган Райс, Обманутая, 2011
Действительно, что-то я раздуваю из мухи слона.
Светлана Головьева, Невеста поневоле
На то они и были специалисты, дабы добывать из обыденных мелочей зерна истины, а может, выращивать из мух слонов.
Ф. Д. Березин, Параллельный катаклизм, 2002
Нечего делать из мухи слона.
Кимберли Лэнг, Не по сценарию, 2012
Известно: мы, женщины, любим сделать из мухи слона, раздуть проблему.
Лидия Филановская, Сияние предметов и людей (сборник), 2007
— Перестань раздувать из мухи слона!
А. В. Устинова, Загадка черной вдовы, 2014
Они могут сделать из мухи слона, копить обиды и излишне остро реагировать в критические моменты.
Патрисия О’Коннелл, Как компании-лидеры избегают бестолковых решений. Преодоление 8 «подводных камней», которые способны разрушить даже непотопляемый бизнес Поддавшись таким мыслям, женщина сделала из мухи слона.
Шефали Тсабари, Дети – зеркало нашего тайного «Я». Как на самом деле сделать счастливыми себя и своих детей!, 2010
Мне хочется сказать: не раздувайте из мухи слона.
Лариса Суркова, Как здорово с ребенком от 1 до 3 лет: генератор полезных советов, 2015
Легко раздувала из мухи слона, чем постоянно его выводила из себя.
Елена Сподина, Дорога судьбы. Повесть
Если у вас есть какие-то очень важные проекты, суперсерьёзные задачи, проверьте, не раздутый ли это из мухи слон.
Алиса Курамшина, Достигатор на халяву, 2014
24glo.com | ▲ | Контакты
Copyright © 24GLO LTD ® 2004-2024. All rights reserved.
Как сделать из мухи слона
Многим известна такая старая добрая игра со словами, сделать из мухи слона. Суть её в том, что нужно из начального слова сделать конечное, на каждом шаге меняя только одну букву, получая при этом на каждом шаге осмысленное существительное.
Известный автор книг по занимательной математике Е. Я. Гик в своей книге «Занимательные математические игры» опубликовал такое 16-ходовое решение, как из мухи сделать слона: муха-мура-тура-тара-кара-каре-кафе-кафр-каюр-каюк-крюк-урюк-урок-срок-сток-стон-слон.
И вот, в один прекрасный день мне довелось заняться решением этой задачи в программном виде.
Из мухи слона, первая версия
Честно признаться, слона из мухи получилось сделать довольно быстро.
Общая идея решения:
— взять словарь существительных
— итеративным алгоритмом пройти от исходного слова в сторону конечного, если получится достичь последнего
— выдать результирующую цепочку, и желательно чтоб она стремилась к минимальной длине
1) Словарь существительных
Оказалось, даже с первым пунктом есть проблемы, — найти стоящий словарь существительных оказалось уже отдельной подзадачей. Не помню где именно, но нашёл сносный готовый словарь. Формат по одному слову на строку, utf8, разделители \r\n — так и оставил в дальнейшем.
2) Алгоритм
Естественно, походя поинтересовался решали ли эту проблему мух и слонов, и как. Хороший вариант решения нашёл тут planetcalc.ru/544. Для только 4 буквенных слов, под яваскрипт (что на самом деле идея правильная для этого приложения — нет смысла гонять серверные мощности, когда поиском может заняться клиентское железо в браузере). Впрочем, исходники не смотрел, а смотрел на здравые рассуждения ниже в статье.
Действительно, если в качестве алгоритма использовать построение дерева со всеми вариантами, пока при прокладке очередного уровня не попадётся искомое слово, то никаких ресурсов не хватит.
Например, у слова КОРА есть 19 переходов только из распространённых слов, пришедших на ум, от «гора» до «корт».
Даже если дать очень оптимистичную оценку на среднее число вариантов модификаций в 5 (всего!), то если к какому-то слову минимальный путь составит 10 шагов, то в памяти должно уместиться дерево в 5 10 ~= 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 поэкономил. Так-то метод задумывался приватным, но для проб и тестов был опубличен. Не пускайте такие штуки в продакшн 🙂 Во всяком случае, без охватывающих проверок.
А конечное слово… может человеческая рефлексия какая-то, а может и интуиция, — оставил возможность использования на потом. Всё же логично ожидать от функции получения набора потомков какой-то зависимости от того, на кого похожими они должны получаться. Ничто не мешает делать первичный отсев прямо тут. Но пока — не используется.
Функция получения возможных мутаций
/** * Получение списка пар для возможных вариантов мутаций * * Для поиска используется рабочий словарь плюс общие вспомогательные словари * * @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 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-й подсловарь можно добавлять разве что после оптимизации хранения словарей, кэширования, алгоритма. А сейчас он только лишнее потребление оперативки.
Но… Но «просто как-то сносно работающий вариант на коленке» меня не устроил. И я продолжил совершенствовать превращение мух в слонов.
*
* Здесь хорошо бы сделать паузу для отдыха глаз, чашка кофе, и в этом духе
*
Слону помадой выкрасила ухо,
Второе, хобот, хвостик и теперь
Летает в спальне розовая муха,
Жужжит и бьется головой о дверь.
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 подсловарей. Один фактор другой не компенсировал. Тем не менее, по сути расширить словарь абсолютно корректный и необходимый ход для приближения к реальным боевым условиям. И есть ещё множество справочников кроссвордиста и словарей, в том числе онлайновых, с которыми можно поработать для расширения нашего словаря.
*
* Вообще, эта задача кажется бесконечной.
* И в этой долгой дороге к совершенству,
* Пожалуй, на этом пятачке стоит сделать ещё один перекур.
*
Некий деятель науки
ДЕЛАТЬ стал СЛОНА из МУХИ:
Надувал, надувал,
Поглядеть народ позвал.
Удивить он всех хотел…
Ну а слон-то улетел!
Версия третья
Честно признаться, ожидал от версии большего. Всё-таки база (была под рукой 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` https://yadi.sk/d/LW_gPhHKkGLdJ">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++?
- И наверняка другие ходы, которые пока ещё не приходили в голову.
PS:
Конечно, в этой статье нельзя не оставить ссылку на то, как делают из мухи слона художники.
Комментарии и замечания приветствуются! Может упустил какие-то простые и важные вещи. Благодарю за внимание.
- из мухи слона
- программирование
- алгоритмы
- оптимизация
- Веб-разработка
- Программирование
- Алгоритмы
Из мухи — слона
В повести известного писателя Юрия Трифонова (1925–1981) «Долгое прощание» рассказывается, как герой проводит время в поезде: «Третьи сутки Ребров, лёжа на верхней полке, мучил себя — делал из мухи слона. На листке бумаги писал: муха — мура — кура — кора — корт — торт — торс. ».
Правила игры очень просты: надо построить цепочку слов от начального (МУХА) до конечного (СЛОН), на каждом шаге меняя только одну букву. При этом могут использоваться только русские 4-буквенные нарицательные существительные в начальной форме: например, слова БАЗА, НОЧЬ, САНИ допускаются, а слова ЛИТЬ, ХОТЯ, РУКУ, НОЧИ, САНЯ, ОСЛО, АБВГ, ФЦНМ — нет (первые два — не существительные, следующие два — не в начальной форме, следующие два — собственные, а не нарицательные, а два последних вовсе не существуют в языке).
Эта игра под названием «Дублеты» приобрела известность благодаря Льюису Кэрроллу — не только автору книг про Алису, но ещё и замечательному математику. В марте 1879 года он начал раз в неделю публиковать в журнале «Ярмарка тщеславия» по три задания в форме броских фраз: «Turn POOR into RICH» — «Преврати бедного в богатого», «Evolve MAN from APE» — «Выведи человека из обезьяны», «Make TEA HOT» — «Сделай чай горячим». В том же году он выпустил брошюру «Дублеты», подробно описал в ней правила и предложил читателям попрактиковаться на нескольких десятках примеров.
Вот и вам пять пар для тренировки — попробуйте построить для них цепочки. Сразу предупреждаю, что в одном случае, скорее всего, не получится: БОРЩ → ПОСТ; ЛИПА → ЖАРА; КИНО → ВАТА; КЛЕН → ЕЛКА; ПАУК → ЛОСЬ.
БОРЩ → БОРТ → ПОРТ → ПОСТ;
ЛИПА → ЛАПА → ПАПА → ПАРА → ЖАРА;
КИНО → ВИНО → ВИНА → ВИЗА → ВАЗА → ВАТА;
ПАУК → ПАРК → ПАРА → КАРА → КОРА → КОЖА → ЛОЖА → ЛОЖЬ → ЛОСЬ;
из КЛЕН получить ЕЛКА нельзя.
Вы наверняка нашли четыре из пяти цепочек, а не смогли построить только одну. Но как доказать, что это действительно невозможно? Может быть, мы просто не придумали способ, а вообще-то он есть. Разобраться нам поможет теория графов.
Первым делом договоримся о том, что именно мы считаем словами, а то может получиться, что я дам вам задание МУХА → СЛОН и вы скажете: «4 хода! МУХА → МУХН → МУОН → МЛОН → СЛОН». Тогда мне придётся со словарями в руках доказывать, что это жульничество, потому что слов МУХН, МУОН и МЛОН не существует. Чтобы избежать этого, мы обратимся к словарю с самого начала и постановим, что будем пользоваться только теми 4-буквенными существительными, которые есть в заранее выбранном источнике. Для этой статьи я взял «Грамматический словарь русского языка» Андрея Зализняка — этот словарь чаще всего применяют в компьютерной лингвистике. Кстати, мысль о том, что очень важно заранее договориться о словаре, пришла в голову ещё Льюису Кэрроллу: 28 из 39 страниц его книги как раз и занимает перечень английских слов, которые можно использовать в игре. Кроме того, условимся, что мы не используем в игре букву Ё и заменяем её на Е.
Всего в «Грамматическом словаре» 1712 четырёхбуквенных существительных. Возьмём, к примеру, существительное ЛОЖЬ и изобразим его точкой. Найдём в словаре все слова, которые отличаются от него на одну букву; их ровно четыре: ЛОЖА, ЛОЖЕ, ЛОСЬ и РОЖЬ. Изобразим их точками, соединёнными со словом ЛОЖЬ; наличие связи означает, что между словами можно перейти за один ход. (Кстати, какую ещё пару слов надо не забыть соединить?) Затем добавим слова, которые за один ход получаются из этих четырёх слов: КОЖА, ЛОЗА, ЛУЖА, ЛЫЖА, РОЖА, РОЛЬ, ЛОСК, — и нарисуем нужные связи.
В итоге у нас получился граф, в котором некоторые из 12 точек (вершин) соединены отрезками (рёбрами). Если нам нужно превратить одно слово в другое, на математическом языке это формулируется так: найти путь между соответствующими вершинами, желательно кратчайший. Так, если нам надо пройти от ЛЫЖА до РОЛЬ, это займёт четыре шага, и пути могут быть разными: ЛЫЖА → ЛОЖА → РОЖА → РОЖЬ → РОЛЬ или ЛЫЖА → ЛОЖА → ЛОЖЬ → РОЖЬ → РОЛЬ. (Докажите, что более короткого пути между словами ЛЫЖА и РОЛЬ нет.)
А теперь изобразим так не 12 слов, а все 1712, и посмотрим, как устроен этот граф. Вручную это сделать едва ли возможно, так что понадобится компьютер. Видно, что на графе выделяется большой кусок, где от любого слова можно дойти до любого другого; в теории графов такой подграф называют компонентой связности. Есть ещё несколько таких кусков поменьше и много точек, которые не связаны вообще ни с чем (такие отдельно стоящие точки тоже можно считать компонентами связности). Ясно, что от одного слова можно дойти до другого тогда и только тогда, когда они входят в одну и ту же компоненту связности.
Самая большая компонента связности включает в себя 1361 слово (то есть 79,5% всех слов). Кроме неё есть компонента размером 11 слов, ещё одна — размером 6 слов, 3 — размером 5 слов, 4 — размером 4 слова, 14 — размером 3 слова, 25 — размером 2 слова и ещё 211 отдельно стоящих слов (АЛОЭ, ВДОХ, ДЖАЗ, НЕБО, ОПЫТ, СОЮЗ, ТАЙМ и другие). Слово КЛЕН входит в большую компоненту связности, а слово ЕЛКА — в маленькую, 5-словную; этим и объясняется тот факт, что из слова КЛЕН не получится ЕЛКА.
Всего в нашем графе 3172 ребра, а значит, у слова в среднем 3172 1712 · 2 = 3,7 соседей. Возвращаясь к самой большой компоненте связности, обратим внимание на то, что из неё торчат «хвосты». Дело в том, что даже в ней у некоторых слов совсем мало соседей. Скажем, от слова ТИГР можно перейти только к слову ТИТР, от него — только к слову ЛИТР, дальше — только к слову ЛИВР (это старинная французская монета, вспомните «Трёх мушкетёров»), дальше — только к слову ЛАВР, а уже от него — к словам МАВР и ЛАВА, после чего возможностей становится резко больше: от слова ЛАВА отходит ещё 5 слов, и мы попадаем в основую гущу вершин.
Таким образом, слово ТИГР — это конец хвоста, и если понадобится пройти из одного такого хвоста в другой, путь может получиться очень длинным, даже если это кратчайший путь между этими двумя вершинами. Самые длинные пути имеют длину 23 — например, от слова ДЖИП до слова ТУЕС (берестяная коробочка) всего 22 шага: ДЖИП → ДЖИН → УЖИН → УДИН → ОДИН → ОВИН → ОВЕН → ОВЕС → СВЕС → СВЕТ → СВАТ → СВАН → СТАН → СТЕН → СТЕК → САЕК → РАЕК → РОЕК → БОЕК → БУЕК → БУЕР → ТУЕР → ТУЕС. Глядя на эту цепочку, вам наверняка хочется пожаловаться: «Я же не знаю половины этих слов!» (признаюсь честно: я тоже не знаю). Но раз мы договорились использовать «Грамматический словарь», то и будем на него опираться, а к борьбе с незнакомыми словами вернёмся чуть позже.
Для 5-буквенных слов английского языка такой граф впервые построил знаменитый американский учёный и автор классических пособий по программированию Дональд Кнут. А почему, кстати, у него 5 букв, а у нас — 4? Есть ли какое-то объяснение тому, что в игру «Из мухи — слона» по-русски обычно играют 4-буквенными словами? Интуитивно кажется, что так интереснее всего. Но попробуем оценить этот интерес и количественно.
Представьте себе, что мы играем однобуквенными словами. В «Грамматическом словаре» ровно 9 однобуквенных существительных: А, Е, И, О, У, Ы, Э, Ю, Я — названия гласных букв (слово Ё мы объединили со словом Е). Из любого слова к любому можно перейти за один ход, и это неинтересно. Если, напротив, играть в 10-буквенные слова, то от большинства слов — как, скажем, от слова БЕЗДЕЛЬНИК, — вообще нельзя никуда перейти. Получается, что игра интересна, когда выполнены два требования: пути между словами длинные и между двумя произвольно взятыми словами путь обычно существует (но не всегда — если успех гарантирован, играть тоже скучно).
Чтобы оценить среднюю длину пути, надо найти самые короткие пути между всеми парами точек, для которых путь есть, и вычислить среднее. Это трудоёмкий процесс, но есть алгоритмы, которые производят такое вычисление достаточно быстро. А сделав его, узнать вероятность успеха совсем просто: у нас есть 1712 4-буквенных слов, а значит, 1712 · 1711 упорядоченных пар (от любого из 1712 слов мы пытаемся пройти к любому из 1711 оставшихся); посчитаем, сколько из них соединены путём, и разделим на 1712 · 1711. Таких пар 1 851 342, а значит, вероятность успеха равна 1 851 342 / (1712 · 1711) ≈ 0,632.
Можно сделать то же самое по-другому, опираясь на знания про размеры компонент связности. Возьмём произвольное начало цепочки; вероятность того, что оно попадёт в большую компоненту связности, составляет 1361/1712; возьмём теперь другое произвольное слово в качестве конца цепочки: в большой компоненте осталось 1360 слов, а всего в словаре — 1711, то есть вероятность того, что оно окажется связанным с началом, составляет 1360/1711. Тогда начало и конец цепочки попадут в большую компоненту с вероятностью 1361 · 1360 / (1712 · 1711). Во вторую по величине компоненту связности они попадут с вероятностью 11 · 10 / (1712 · 1711). Суммируя эти вероятности для всех компонент, получим то же число 0,632. Результаты подсчётов для слов от 1 до 12 букв — в таблице:
Длина слова
Количество слов
Средняя длина пути
Вероятность успеха
1
9
1
1
2
70
3,6
1
3
490
4,4
0,866
4
1712
8,8
0,632
5
3642
8,6
0,076
6
5120
7,9
0,004
7
6584
8,9
0,002
8
6929
3,3
0,0001
9
6349
2,2
0,00008
10
5098
1,3
0,00003
11
3808
1,5
0,00004
12
2747
1,2
0,00002
Видно, что 4-буквенные слова действительно обеспечивают хорошую, но всё же не стопроцентную вероятность успеха и при этом создают достаточно длинные цепочки. А с 10-буквенными словами всё скучно: даже в тех редких случаях, когда путь есть, он обычно состоит из одного шага (ВОЗМЕЩЕНИЕ → ВОЗМУЩЕНИЕ), редко — из двух или больше. Единственный путь из пяти шагов соединяет слова ПАССИРОВКА и ФАРШИРОВКА: ПАССИРОВКА → МАССИРОВКА → МАСКИРОВКА → МАРКИРОВКА → МАРШИРОВКА → ФАРШИРОВКА.
Эта цепочка напоминает ещё об одной проблеме, с которой надо разобраться: редкие слова. Попробуйте решить такую задачу: ДАЛЬ → ПАРИ. В этих словах совпадает буква А на втором месте, и есть надежда справиться за три шага. Действительно, такой путь есть: ДАЛЬ → ПАЛЬ → ПАЛИ → ПАРИ. Но едва ли он вас порадует: большинство людей не знают ни слова ПАЛЬ (‘выжженный участок в лесу или в степи’), ни слова ПАЛИ (один из древних индийских языков). Но существует и путь из более нормальных слов: ДАЛЬ → ДАНЬ → ДЕНЬ → ТЕНЬ → ТЕНТ →ТЕСТ → ТОСТ → ПОСТ → ПОРТ → ПОРА → ПАРА → ПАРИ. Он длиннее, но в каком-то смысле лучше пути из трёх шагов. Попробуем формализовать эту идею.
Для этого нам понадобится ещё один словарь — частотный (я пользуюсь «Новым частотным словарём русской лексики» О. Ляшевской и С. Шарова). В частотном словаре слова упорядочены по тому, насколько они употребительны в языке: 1-е место занимает союз И, на 2-м месте — предлог В, на 3-м — частица НЕ и т. д. А вот 10 самых частых 4-буквенных существительных с указанием их мест: 65) ДЕЛО, 71) ДЕНЬ, 74) РУКА, 104) ЛИЦО, 106) ДРУГ, 110) ГЛАЗ, 140) СИЛА, 191) ВОДА, 192) ОТЕЦ, 205) НОГА.
Слова типа ДЖИП и ТИТР стоят гораздо ниже: 6616) ДЖИП, 8086) ТИТР. Всего в этом словаре 52 138 слов, из них с «Грамматическим словарём» пересеклось 1140 4-буквенных существительных. А, например, слово ЛИВР (старая французская монета) даже не попало в частотный словарь. Условно присвоим ему и всем другим таким словам номер 100000.
А теперь сделаем наш граф ориентированным и взвешенным. Ориентированный — это значит, что из вершины в вершину будут вести не отрезки, а стрелки, точнее пары стрелок: одна в одну сторону, другая в другую. А взвешенный значит, что каждой стрелке будет приписан вес: по одним стрелкам ходить будет дороже, а по другим дешевле. Веса припишем так: если стрелка ведёт в слово, которое занимает k-е место в частотном словаре, припишем ей вес k (мы могли бы выбрать и какую-нибудь другую функцию, но квадратный корень даёт результаты, которые кажутся подходящими для наших нужд). Например, все стрелки, ведущие в ДЕЛО, получают вес 65 ≈ 8,1 , все стрелки, ведущие в ТИТР, — 8086 ≈ 89,9 , а все стрелки, ведущие в ЛИВР, — 100000 ≈ 316,2 . Длиной пути теперь будет не количество рёбер, а сумма чисел на стрелках, по которым мы двигались. Проходить редкие слова теперь невыгодно: ведущие в них стрелки весят слишком много.
Попробуем для примера найти оптимальный путь от слова ЛОЖЬ к слову РОЖА. Возьмём подграф, содержащий слова ЛОЖЬ, РОЖЬ, ЛОЖА и РОЖА, и разметим в нём веса.
Окажется, что путь ЛОЖЬ → РОЖЬ → РОЖА стоит 121,6 + 78,6 = 200,2, а путь ЛОЖЬ → ЛОЖА → РОЖА стоит 82,6 + 78,6 = 161,2. Иначе говоря, выгоднее идти через более частое слово ЛОЖА, чем через более редкое РОЖЬ.
Но вернёмся к путям от ДАЛЬ к ПАРИ. Оказывается, более длинный по числу шагов путь выгоднее с точки зрения весов: ДАЛЬ → 96,5 ДАНЬ → 8,4 ДЕНЬ → 36,4 ТЕНЬ → 140,9 ТЕНТ → 65,8 ТЕСТ → 81,6 ТОСТ → 38,8 ПОСТ → 58,4 ПОРТ → 16,6 ПОРА → 27,9 ПАРА → 126,2 ПАРИ (сумма 697,5); ДАЛЬ → 316,2 ПАЛЬ → 316,2 ПАЛИ → 126,2 ПАРИ (сумма 758,6).
Так мы формализовали ощущение, почему длинная цепочка с известными словами лучше, чем короткая с неизвестными. Кстати, для задачи МУХА → СЛОН цепочки без весов и с весами тоже разные. Без весов (10 шагов): МУХА → МУРА → МАРА → ПАРА → ПАРК → ПАЕК → САЕК → СТЕК → СТЕН → СТОН → СЛОН; с весами (13 шагов): МУХА → МУКА → ЛУКА → ЛУПА → ЛАПА → ПАПА → ПАРА → ПАРК → ПАЕК → САЕК → СТЕК → СТОК → СТОН → СЛОН.
Увы, и в цепочке с весами не удалось обойтись без малоизвестного слова САЕК (точнее, САЁК), которое значит ‘молодой олень’. Но другие решения этой задачи включают в себя ещё и не такое. Самую короткую из известных цепочек придумал Владимир Гончаров; в ней 7 шагов: МУХА → МУЛА → КУЛА → КИЛА →КИЛН → КИОН → СИОН → СЛОН. По нашим правилам она не подходит, потому что в «Грамматическом словаре» из 6 промежуточных слов есть только КИЛА (это разговорное название для грыжи), а если бы они и были, то с весами эта цепочка стоила бы очень дорого, ведь все промежуточные слова в ней редкие — да и разве интересна цепочка, в которой 6 из 6 промежуточных слов нам неизвестны?
Всё сказанное выше, с одной стороны, звучит неутешительно: игру «из мухи — слона» постигла судьба шахмат и шашек — компьютер играет в неё гораздо лучше человека. С другой стороны, не всё так плохо: компьютерный анализ позволил нам узнать много интересного и про саму игру, и про русский язык.
Художник Мария Усеинова
Как из мухи сделать слона.
Последовательно преобразует одно 4-х буквенное слово в другое, изменяя одну букву предыдущего слова на каждом шаге.
Недавно ребенок принес из школы задачку. В пятом классе на уроках русской словесности детям задают такие задания: составить цепочку слов, каждое последующее из которых, отличается от предыдущего всего на одну букву. Изначально задано первое и последнее слово цепочки. Решив прекратить мучения любимой дочки, которая в течение нескольких часов тщетно пыталась сделать из мухи слона, я написал следующий калькулятор:
Преобразование 4-х буквенных слов при помощи генетического алгоритма
Начальное слово
Слово из которого надо получить второе слово
Конечное слово
Слово в которое требуется преобразовать первое слово
Максимальная длина цепочки
Размер популяции
Максимальное количество элементов в каждом поколении
Рассчитать
Файл очень большой, при загрузке и создании может наблюдаться торможение браузера.
Загрузить
Ссылка Сохранить Виджет
Описание решения
Поначалу я применил «грубую силу» и попробовал решить задачу в лоб. Суть моего наивного метода сводилась к построению дерева слов, полученных путем перебора всех букв русского алфавита и подстановке их вместо одной из букв предыдущего слова (см. рисунок).
Каждое новое слово проверялось на отсутствие среди предшествующих, а также на наличие в словаре, который я перенес с сайта любителей кроссвордов в наш справочник Слова из 4-х букв (надеюсь, авторы сайта меня простят за эту вольность).
Далее, успешно проверенное слово включалось в дерево и для него снова проводилась аналогичная процедура, до тех пор, пока не будет найдено искомое слово.
С первого раза, конечно же, ничего не заработало — мой рекурсивный алгоритм быстренько переполнил ограниченный стек джаваскрипта. Преобразование рекурсивного алгоритма в циклический дало более удачный результат — муха была трансформирована в слона минут этак за 10.
Полученный результат был пригоден для дочки, но не для меня. К тому же, пока работала программа, у меня было достаточно времени поразмыслить над улучшением алгоритма и гипотетической возможностью мухи эволюционировать в слона. Этот программно-биологический бред в конечном итоге привел меня к генетическому алгоритму, который как нельзя кстати подошел для решения этой задачи и переродил муху в слона в течение нескольких секунд.
Генетический алгоритм
Генетическим алгоритм был назван так из-за сходства процесса поиска решения с биологической эволюцией. Решением задачи является вектор слов, удовлетворяющих некоторому критерию (хромосома). На каждом шаге мы порождаем несколько таких векторов (популяцию), после чего осуществляем отбор наиболее пригодных вариантов (жизнеспособных особей), т. е. выполняем селекцию. На последующем шаге ранее полученные варианты снова видоизменяются, порождаются новые варианты (происходит мутация) и так до тех пор, пока не будет выполнен критерий останова алгоритма (в нашем случае муха преобразуется в слона).
По сути, мой начальный алгоритм тоже можно было отнести к генетическим (селекция осуществлялась путем проверки по словарю), но так как число порожденных вариантов увеличивалось на каждом шаге, то в конечном итоге всей популяции новых особей для дальнейшего существования не оставалось жизненного пространства (ресурсов процессора).
В модифицированном алгоритме была применена улучшенная функция селекции, которая отбирает только самые похожие на конечное слово варианты. Количество самых жизнеспособных вариантов задается параметром Размер популяции, чем меньше это число, тем быстрее работает алгоритм, чем больше — тем качественнее получается результат.
В качестве дополнительного критерия останова было введено ограничение на максимальный размер цепочки, для этого был введен еще один параметр. Алгоритм остановится, если после воспроизводства заданного числа поколений не будет получен искомый результат.
Функция приспособленности (похожести текущего слова на конечное) оценивала каждый вариант по 12 бальной шкале.
- за каждую букву, совпадающую по положению и значению с конечным результатом, начислялось 3 балла
- если гласная буква слова находилась на том же месте, что и другая гласная буква искомого слова — 2 балла
- и один балл начислялся просто за наличие гласной буквы.
Таким образом, конечное слово СЛОН оценивалось в 12 баллов, а начальная МУХА всего в 2.
Желающие более детально ознакомиться с алгоритмом, могут это сделать, путем исследования содержимого функции calculate из javascript'а этой страницы.
P.S.
Один наш пользователь, увлекающийся построением подобных цепочек, попросил сделать Преобразование 5-и буквенных слов перестановкой одной буквы. Этот онлайн калькулятор берет 5-и буквенные слова из справочника: Слова из 5-и букв
