Trie по сравнению с суффиксным деревом по сравнению с суффиксным массивом
Какая структура обеспечивает лучшие результаты проверки производительности; trie (дерево префикса), суффиксное дерево или суффиксный массив? Есть ли другие подобные структуры? Что такое хорошие реализации Java этих структур?
Править: в этом случае я хочу сделать сопоставление строк между большим словарем имен и большим набором текстов естественного языка для идентификации названий словаря по текстам.
2 ответа
Используя деревья суффиксов, вы можете написать что-нибудь, что будет соответствовать вашему словарю вашему тексту за O (n + m + k) времени, где n - буквы в вашем словаре, m - буквы в вашем тексте, а k - количество совпадений. . Для этого попытки выполняются намного медленнее. Я не уверен, что такое Suffix Array, поэтому не могу это комментировать.
Тем не менее, кодить нетривиально, и я не знаю ни одной библиотеки Java, обеспечивающей необходимые функции.
РЕДАКТИРОВАТЬ: В этом случае я хочу выполнить сопоставление строк между большим словарем имен и большим набором текстов на естественном языке, чтобы идентифицировать имена словаря в текстах.
Это похоже на приложение для алгоритма Ахо-Корасика : построить автомат из словаря (в линейном времени), который затем может быть использован для поиска всех вхождений любого из словарных слов в несколько текстов (также в линейном времени).
(Описание в этих конспектах лекции , на которые есть ссылка в разделе «Внешние ссылки» на странице Википедии, намного легче читать, чем описание на самой странице.)
{{ 1}}