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

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

3 голосов
/ 15 марта 2012

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

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

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

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

То, что я пробовал:

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

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

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

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

Ответы [ 4 ]

2 голосов
/ 15 марта 2012

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

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

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

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

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

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

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

1 голос
/ 16 марта 2012

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

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 шагов во втором случае).

1 голос
/ 15 марта 2012

Возможно, есть и лучшие способы, но это не в моей голове:

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

id    name       a    b  ...  l  ...  n  ...  o
1     balloon    1    1       2  ...  1  ...  2

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

// User enters 'zqlamonrlob'
// You count the letters:
a b c d e f g h i j k l m n o p q r s t u v w x y z
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'] ...}";

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

0 голосов
/ 15 марта 2012

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

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

...