Более эффективный способ найти фразы в строке?

Question

У меня есть список, который содержит 100 000+ слов / фраз, отсортированных по длине

let list = [“string with spaces”, “another string”, “test”, ...]

Мне нужно найти самый длинный элемент в списке выше, который находится внутри данного предложения. Это мое первоначальное решение

for item in list {
    if sentence == item
        || sentence.startsWith(item + “ “) 
        || sentence.contains(“ “ + item + “ “) 
        || sentence.endsWith(“ “ + item) {
        ...
        break
    }
}

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

Answer 1

Вы можете создать поисковик Aho-Corasick из списка, а затем запустить это предложение. Согласно https://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_algorithm "Сложность алгоритма линейна по длине строк плюс длина искомого текста плюс количество найденных совпадений. Обратите внимание, что, поскольку все совпадения найдены, может быть квадратичное c количество совпадений, если каждая подстрока соответствует (например, словарь = a, aa, aaa, aaaa и входная строка aaaa). "

Answer 2

Я решил использовать решение Tr ie https://en.wikipedia.org/wiki/Trie. Каждый узел в tr ie - это слово, и все, что я делаю, это делаю токенизацию входного предложения (по слову) и пересекаю tr ie.

. Это улучшило производительность с ~ 140 секунд до ~ 5 секунд

Answer 3

Я бы разбил данное предложение на список слов, а затем вычислил все возможные смежные подсписки (то есть фразы). Учитывая предложение из n слов, в нем можно найти n * (n + 1) / 2 возможных фраз.

Если вы теперь замените свой список поисковых фраз ([“string with spaces”, “another string”, “test”, ...]) на (амортизированное) постоянное время просматривая структуру данных, как хэш-набор, вы можете просмотреть список фраз, которые вы вычислили на предыдущем шаге, и проверить, есть ли каждая из них в наборе за ~ постоянное время.

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