Нахождение самого длинного словарного слова в конце строки

Question

Я ищу лучший способ поиска в строке буквенных символов самого длинного словарного слова в конце строки.

Пример: Для строки qbehugejackhammer результат должен быть jackhammer вместо hammer.

Один из способов сделать это несколько эффективнее - хранить слова в обратном виде в индексированной таблице и повторять их по одной букве за раз, пока они больше не будут соответствовать чему-либо:

SELECT word FROM dictionary WHERE word LIKE 'remmahkca%';
SELECT word FROM dictionary WHERE word LIKE 'remmahkcaj%'; # last match
SELECT word FROM dictionary WHERE word LIKE 'remmahkcaje%';

Это выглядит и выглядит как хак и, скорее всего, не является оптимальным решением. Есть ли более быстрый и / или более хороший способ сделать это? Моими инструментами выбора являются PHP и MySQL, но если какой-то другой язык или СУБД лучше соответствуют моим потребностям, у меня все на слух.

Answer 1

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

SELECT word FROM dictionary WHERE word = 'qbehugejackhammer'; --no match
SELECT word FROM dictionary WHERE word = 'behugejackhammer'; --no match
SELECT word FROM dictionary WHERE word = 'ehugejackhammer'; --no match
SELECT word FROM dictionary WHERE word = 'hugejackhammer'; --no match
--...
SELECT word FROM dictionary WHERE word = 'jackhammer'; --found it!

Answer 2

Это может показаться немного злым, но вы, вероятно, получите лучшую производительность, загрузив свой словарь в массив в форме дерева словарей, но в обратном порядке слов, например:

array(
    'r' => array(
        'u' => array(), // -- words ending in 'ur' would end up in here
        'a' => array(), // -- words ending in 'ar' would end up here
        'e' => array( // -- words ending in 'er' would end up in here
            'm' => array(
                'm' => array(
                      // -- jackhammer will be kept further up here

Тогда ищем.

$reverseWord = ""; // -- Incoming 'word' string goes here, in reverse.
$dictionary = [structure above];
$dictionaryPosition = $dictionary;
$dictionaryHistory = "";

for( $i = 0, $l = strlen($reverseWord); $i < $l; $i++ ) {
    $char = $reverseWord[$i];

    // -- If this character doesn't exist in this dictionary position, we've reached the end
    if( !isset($dictionaryPosition[$char]) )
        break;

    // -- log this character
    $dictionaryHistory = $char . $dictionaryHistory;

    // -- Climb up the tree
    $dictionaryPosition = $dictionaryPosition[$char];
}

// -- $dictionaryHistory now contains the word you're looking for.

Каждый массив должен содержать не более 26 записей (при условии, что используются только буквенные символы), так что вы смотрите на то, чтобы сделать максимум 26 * n поисков по одному символу каждый. Даже с глубиной слова 20 символов это бесконечно лучше, чем повторять список из 50 тысяч слов несколько раз.

Answer 3

Быстрый хакерский ответ: загрузите ваш словарь в map или любую другую структуру данных, эквивалентную php (английский словарь содержит всего ~ 50 тыс. Слов, легко помещается в RAM v, а карта намного, намного быстрее запрашивает чем вызов БД). Затем выполняйте итерацию вперед по 1 символу за раз, проверяя каждую подстроку на карте, пока не найдете совпадение.

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

Редактировать:"карта" должна быть "установлена".

Answer 4

Загрузить словарь в массив PHP. Для каждого входного слова используйте in_array ( ссылка ) для последовательно меньших подстрок, как описано ниже, пока не найдете совпадение.

Например, рассмотрим ваш ввод qbehugejackhammer. Сначала ищите в массиве значение qbehugejackhammer, затем значение behugejackhammer, затем значение ehugejackhammer и т. Д., Пока не найдете совпадение. Вы можете остановиться, как только найдете первый матч.