сравнить зашифрованные слова с нешифрованным списком слов php

Question

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

зашифрованное слово "lonbayb", а где-то в списке слов есть слово "вавилон". скрипт должен показать мне расшифрованное слово

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

Answer 1

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

"babylon" ==> "abblnoy"

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

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

Answer 2

Чтобы перемешать слова, используйте 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 ГГц, и он завершит 10000 вызовов findWords () в наборе 10000 слов всего за 0,08 секунды. Другая версия займет 207 секунд. См ревизию для старой версии.