Улучшение соответствия слов (смотрите в будущее)

Question

Я пытаюсь воспроизвести функциональность текстовой аннотации на http://mandarinspot.com/annotate, и у меня есть решение, но мои усилия отстают с точки зрения скорости.Я посмотрел на алгоритмы поиска строк, и методы различаются для каждого приложения, поэтому я ищу здесь несколько указателей.

Эта страница содержит кусок китайского языка и добавляет произношение пиньинь вверху, а также подсказку для определения.Причины, по которым я хочу воспроизвести эту страницу: 1. Мне нравится использовать другую фонетическую систему под названием Gwoyeu Romatzyh, и 2. для повторного изучения программирования.

Я попытаюсь описать, что я делаю,замена основного китайского языка на английский.Допустим, для заданной строки «Гари съел виноград и грейпфрут» программа должна вывести определение для каждого слова, например: «[собственное имя] [принимать пищу] [фрукты растут группами] [крупные цитрусовые фрукты]»,Теперь, когда слова «грейпфрут» и «грейпфрут» начинаются одинаково, программа должна их различать (на китайском языке пробелов нет, поэтому разделение строки не вариант, поэтому на самом деле мне придется проанализировать «Garyateagrapeandagrapefruit»)он "смотрит в будущее" при разборе "грейпфрута").

Моя структура данных - это древовидная структура, в которой каждый узел содержит один китайский символ и родительский идентификатор.Если этот символ является частью фразы, родитель сообщает мне, каким был предыдущий символ фразы.

Пример: если «ABC» - это китайское слово, A может иметь идентификатор 1, а родительский идентификатор отсутствует,B: ID = 2 и родитель = 1, и C: ID = 3, родитель = 2.Для «ABD» D будет иметь ID = 4 и parent = 2 (B).Каждый узел также имеет массив 'Definition', который указывает на отдельный массив, содержащий английское определение для этого символа или слова.«Определение» будет пустым, если узел не является последним для слова.

Для разбора строки:

1. Содержит текущий символ (curChar) и символпосле него (nextChar), до двух переменных.
2. Поиск узла, где nextChar соответствует символу узла, и этот узел имеет curChar в качестве родителя.Если это правда, я полагаю, что у меня есть длинное слово из двух или более символов.Если это неверно, я делаю вывод, что между curChar и nextChar нет никакой связи, и вывожу все, что у меня было до curChar.

Спасибо за любой совет!

Answer 1

Aho-Corasick в Википедии даст вам быстрый алгоритм, который находит все слова из словаря, когда они появляются в потоке.Учитывая это, вы можете выбрать самые длинные альтернативы, как вы это делали, или использовать динамическое программирование, чтобы найти путь по найденным словам, который учитывает все символы в потоке.

Answer 2

Просто предложение - как насчет использования хеш-таблицы вместо дерева?Это повысило бы эффективность поиска, если бы вы использовали ее в сочетании с циклическим хешем (как тот, который используется в алгоритме поиска строк Рабина-Карпа), так что вычисление хеша занимает O (1) на подстроку, а поиск занимает среднеедело O (1).