[recovery mode] Как сделать из мухи слона13.11.2015 18:33

  /**
        * Поиск цепочки побуквенных преобразований от первого слова ко второму
        *
        * Возвращает список слов или пустой массив если цепочки преобразований не существует
        *
        * @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;
        }

   /**
        * Функция оценки похожести слова
        *
        * @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;
        }

  /**
        * Получение списка пар {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;
        }

/**
* Двоичный поиск в сортированном массиве
*
* @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);
}

                     // Сортируем новое поколение по "степени приспособленности" (похожести последнего слова цепочки на искомое)
                        usort($mutationChains, function($a, $b) {
                                $diff = $b['score'] - $a['score'];
                                return $diff ? $diff : mt_rand(-1, 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);
        }

--
-- База данных: `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 ;

        ...

        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'];
        }