Как выполнить поиск символа в любом порядке (12 букв, из которых 6 должно быть слово) с PHP?

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

например, у меня есть эти буквы: efjlnrrttuwx (12 букв)

Я ищу это слово TURTLE (6 букв)

Как найти все возможные слова в полном диапазоне (12 слов) с помощью php? (Или с python, если это может быть намного проще?)

Вещи, которые я пробовал:

  • Использование перестановок: я сделал все возможные строки, используя алгоритм перестановки, поместив их в массив (только 6 символов длиной) и сделайте in_array, чтобы проверить, совпадает ли оно с одним из слов в моем массиве с допустимыми словами (в этом случае, содержащие TURTLE, но иногда два или три слова). Этот калькулятор стоит много памяти и времени, особенно с 6 + символами, чтобы получить перестановки.

  • создавая регулярное выражение (я плохо в этом). Я хотел создать регулярное выражение, чтобы проверить, находится ли 6 из 12 (входных) символов в слове из «действительного массива». проблема в том, что мы не знаем, какая буква из 12 будет исходной позицией и позицией других слов.

Примером этого может быть: http://drawsomethingwords.net/

Надеюсь, вы можете помочь мне с этой проблемой, так как я действительно хотел бы это исправить. Спасибо за все ваше время 🙂

Я сталкивался с подобными проблемами при написании редактора кроссвордов (например, найти все слова длины 5 с «В» во второй позиции). В основном это сводится к:

  • Обработать список слов и упорядочить слова по длине (т. Е. Список всех слов длины 2, длины 3, длины 4 и т. Д.). Причина в том, что вы часто знаете длину слова (ов), которое вы хотите найти. Если вы хотите найти слова неизвестной длины, вы можете повторить поиск снова для другого списка слов.
  • Вставьте каждый отдельный список слов в дерево третичного поиска, что значительно ускорит поиск слов. Каждый узел в дереве содержит символ, и вы можете спуститься к дереву для поиска слов. Существуют также специализированные структуры данных, такие как trie, но я еще не изучил (пока).

Теперь для вашей проблемы вы можете использовать дерево поиска для записи функции поиска, такой как

function findWords($tree, $letters) { // ... } 

где treetree поиска, содержащее слова длины, которую вы хотите найти, а letters – список допустимых символов. В вашем примере letters будет строка efjlnrrttuwx .

Дерево поиска позволяет вам искать слова, по одному символу за раз, и вы можете отслеживать символы, с которыми вы столкнулись. Пока эти символы находятся в списке допустимых букв, вы продолжаете поиск. Когда вы столкнулись с листовым узлом в дереве поиска, вы нашли существующее слово, которое вы можете добавить к результату. Если вы столкнулись с символом, который не находится в letters (или он уже использовался), вы можете пропустить это слово и продолжить поиск в другом месте в дереве поиска.

Мой редактор кроссвордов Palabra содержит реализацию вышеуказанных шагов (часть выполняется на Python, но в основном на C). Он работает достаточно быстро для списка слов по умолчанию Ubuntu, содержащего примерно 70 тыс. Слов.

Есть, вероятно, лучшие способы, но это просто не в моей голове:

Я предполагаю, что у вас есть база данных слов (например, словарь). Добавьте поля az в таблицу базы данных. Напишите сценарий, который суммирует количество каждой буквы в слове и записывает их в поля az как целое число. IE для воздушного шара, таблица будет выглядеть так:

 id name ab ... l ... n ... o 1 balloon 1 1 2 ... 1 ... 2 

Затем, когда пользователь вводит слово, вы подсчитываете, сколько из каждого символа находится в этом слове и соответствует тому, что находится в базе данных.

 // User enters 'zqlamonrlob' // You count the letters: abcdefghijklmnopqrstu vwxyz 1 1 0 0 0 0 0 0 0 0 0 2 1 1 2 0 1 1 0 0 0 0 0 0 0 1 // Query the database $sql = "SELECT `name` FROM `my_table` WHERE `a` <= {$count['a'] AND `b` <= {$count['b'] ...}"; 

Это даст вам список слов, которые используют некоторые или все буквы, введенные пользователем.

Вот регулярное выражение, просто чтобы показать, что он может (но не обязательно должен ) быть выполнен:

 preg_match('/^(?:t()|u()|r()|t()|l()|e()|.)+$\1\2\3\4\5\6/i', 'efjlnrrttuwx') 

Матчи.

Как это работает? Пустые скобки для скобок всегда совпадают, если соответствует предыдущее письмо. Обратные ссылки в конце регулярного выражения удостоверяются, что каждый из символов участвовал в матче. Следовательно,

 preg_match('/^(?:t()|u()|r()|t()|l()|e()|.)+$\1\2\3\4\5\6/i', 'efjlnrrtuwx') 

(правильно) не будет соответствовать, потому что в строке есть только один t но для регулярного выражения требуется два разных t s.

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

Я думаю, вам нужно подойти к этой проблеме с противоположного направления.

Прокрутите список слов, проверяя слова с указанным количеством символов, чтобы увидеть, находятся ли слова в указанном наборе символов.