сравнить омлет слова со нескремблированным списком слов PHP

Question

Я ищу способ сравнения закодированные слов с словником полного нескремблированных слов, например:

зашифрованного словом является «lonbayb» и где-то в словнике является словом «Babylon ». сценарий должен показывать мне расшифрованное слово

любая идея, как решить эту проблему?

Answer 1

Чтобы перетасовать слова, используйте str_shuffle(). Чтобы сравнить перетасованную строку со списком слов, вы можете использовать count_chars().

class WordFinder 
{ 
    protected $_wordList; 
    protected $_map; 

    public function __construct(array $wordList) 
    { 
     $this->_wordList = $wordList; 
    } 

    protected function _initMap() 
    { 
     if(!is_array($this->_map)) { 
      $this->_map = array(); 
      foreach($this->_wordList as $word) { 
       $key = count_chars($word, 3); 
       if(!isset($this->_map[$key])) { 
        $this->_map[$key] = array(); 
       } 
       $this->_map[$key][] = $word; 
      } 
     } 
    } 

    public function findWords($searchWord) 
    { 
     $searchWord = count_chars($searchWord, 3); 
     $this->_initMap(); 
     if(isset($this->_map[$searchWord])) { 
      return $this->_map[$searchWord]; 
     } 
     return false; 
    }  
} 

Затем сделайте

$list = array('evil', 'live', 'vile', 'cat'); 
$finder = new WordFinder($list); 
var_dump($finder->findWords('evli')); 

И это вернет

array(3) { 
    [0]=> 
    string(4) "evil" 
    [1]=> 
    string(4) "live" 
    [2]=> 
    string(4) "vile" 
} 

EDIT Я обменялся исходный код с этой версии, так как он выполняет гораздо лучше большие текстовые списки. Я протестировал выше на моем 2,2 Ghz Dual Core и завершил 10000 вызовов findWords() в коллекции из 10000 слов всего за 0,08 секунды. Другая версия займет 207 секунд. См. Версию для старой версии.

Answer 2

Простым решением, которое приходит на ум, является сортировка букв как скремблированных, так и с расшифровкой слов в алфавитном порядке перед сравнением. Я называю это «перетасовки»:

"babylon" ==> "abblnoy" 

В практическом плане, вы должны создать второй список слов из вашей ссылки словника, со ссылкой словник, имеющие свои записи перемешиваются, как это.

, а затем, когда вы смотрите на новое слово и хотите узнать, находится ли он в списке, перетасуйте его таким же образом, и вы можете выполнить простой поиск в вашем перетасованном списке ссылок. Если вы сортируете слова в перетасованном списке ссылок по алфавиту, вы можете даже выполнить двоичный поиск на нем. Или вы помещаете перетасованные опорные слова в хешсет или b-дерево ... все, что легко быстро найти.