Реализация сопоставления с образцом в дереве tr ie - PullRequest
Новая
       83

Реализация сопоставления с образцом в дереве tr ie

0 голосов
/ 22 апреля 2020

В настоящее время я использую реализацию tr ie из этого сообщения о переполнении стека:

Получение списка слов из Tr ie

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

EX: если шаблон, который я ищу, это: CH ?? S? и это подмножество словаря, которое соответствует моему начальному префиксу: {CHABAD, CHACHA, CHARIOT, CHATTED, CHEATER, CHOMSKY, CHANEL CHAFED, CHAFER, CHAINS, CHAIRS, CHEESE, CHEESY CHRONO, CHUTES, CHISEL}

* * Я бы искал tr ie с префиксом 'CH', а затем отфильтровал слова, которые соответствуют моему желаемому шаблону CH ?? S? (CHEESY, CHEESE, CHISEL) и верните их.

Мне интересно, есть ли более быстрый способ сделать это, чтобы избежать использования регулярного выражения в последнем шаге. Я думал, что мог бы использовать дерево суффиксов ( алгоритм дерева суффиксов Укконена в простом английском языке sh) или алгоритм Бойера-Мура, но ни тот, ни другой не работают, потому что они ищут по суффиксам, а не по шаблонам.

1 Ответ

1 голос
/ 22 апреля 2020

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

FindMatches(pattern P, tree T) {
    if (tree is empty) {
        return that there are no matches;
    }

    if (pattern is empty) {
        report a match if T is a word;
    } else if (pattern[0] is a letter) {
        FindMatches(P[1:], T.childFor(pattern[0]));
    } else if (pattern[0] is ?) {
        for (each child C of T) {
             gather matches from FindMatches(P[1:], C);
        }
        report all matches found this way;
    } else {
        something is wrong with your pattern;
    }
}

Ваш подход простого сопоставления CH следует вместе с этим подходом. Однако, когда вы подходите к точке, где вы сопоставляете ? символов, ваш подход просто использует DFS, чтобы найти все слова ниже текущей точки, тогда как этот подход вместо этого просто разветвляется на один уровень и собирает совпадения. Другими словами, этот подход представляет собой гибрид между «следовать за одним символом за раз, если есть четкий символ для подражания» и «исследовать все поддерево в поисках совпадений», фокусируя ветвление стратегически.

...