Алгоритм Word Prediction

Я уверен, что на этом есть сообщение, но я не мог найти ответ на этот точный вопрос. Рассмотрим следующее:

• У нас есть словарь для словаря
• Мы накормили много абзацев слов, и я хочу уметь предсказать следующее слово в предложении, учитывая этот ввод.

Скажем, у нас есть несколько предложений, таких как "Привет, меня зовут Том", "Его зовут Джерри", "Он идет туда, где нет воды". Мы проверяем хеш-таблицу, если существует слово. Если это не так, мы присваиваем ему уникальный идентификатор и помещаем его в хэш-таблицу. Таким образом, вместо того, чтобы хранить "цепочку" слов как связку строк, мы можем просто иметь список уникальных идентификаторов.

Выше было бы, например, (0, 1, 2, 3, 4), (5, 2, 3, 6) и (7, 8, 9, 10, 3, 11, 12). Обратите внимание, что 3 - это "есть", и мы добавили новый уникальный идентификатор, когда обнаружили новые слова. Так скажите, что нам дается предложение "ее имя", это будет (13, 2, 3). Мы хотим знать, учитывая этот контекст, что должно быть следующим словом. Это алгоритм, о котором я думал, но я не считаю его эффективным:

• У нас есть список N цепей (наблюдаемые предложения), где цепочка может быть ex. 3,6,2,7,8.
• Каждая цепочка имеет средний размер M, где M - средняя длина предложения
• Нам дана новая цепочка размера S, например. 13, 2, 3, и мы хотим знать, что является наиболее вероятным следующим словом?

Алгоритм:

• Сначала сканируйте весь список цепей для тех, кто содержит полный вход S (13,2,3, в этом примере). Поскольку нам приходится сканировать N цепей, каждая из которых равна длине M, и сравнить S букв за раз, ее O (N * M * S).

• Если в нашем скане нет цепей, которые имеют полное S, следующее сканирование, удалив наименее значимое слово (т.е. первое, так что удалите 13). Теперь сканируйте (2,3) как в 1 в худшем случае O (N * M * S), который действительно S-1.

• Продолжайте сканирование таким образом, пока мы не получим результаты > 0 (если вообще).

• Подсчитайте следующие слова во всех оставшихся цепочках, которые мы собрали. Мы можем использовать хеш-таблицу, которая рассчитывается каждый раз, когда мы добавляем, и отслеживаем наиболее добавленное слово. O (N) в худшем случае, O (1), чтобы найти максимальное слово.

• Максимальное найденное слово является наиболее вероятным, поэтому верните его.

Каждое сканирование занимает наихудший случай O (M * N * S). Это связано с тем, что существует N цепей, каждая цепочка имеет номера M, и мы должны проверить S-номера для наложения соответствия. Мы сканируем S раз худший случай (13,2,3, затем 2,3, затем 3 на 3 сканирования = S). Таким образом, общая сложность равна O (S ^ 2 * M * N).

Итак, если у нас есть 100 000 цепей и средняя длина предложения 10 слов, мы смотрим на 1,000,000 * S ^ 2, чтобы получить оптимальное слово. Ясно, что N → M, поскольку длина предложения не масштабируется с числом наблюдаемых предложений вообще, поэтому M может быть константой. Тогда мы можем уменьшить сложность до O (S ^ 2 * N). O (S ^ 2 * M * N) может быть более полезным для анализа, так как M может быть значительной "константой".

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

Ответы

The wrath sing, goddess, of Peleus' son, Achilles

START START the
START the wrath
the wrath sing
wrath sing goddess
goddess of peleus
of peleus son
peleus son achilles