ハエから象を作る方法

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