Как найти фразы внутри большого текста, используя C?

Question

Замечание : я знаю, что есть много похожих вопросов по SO, но нет специфических для языка C, поэтому я и задаю этот вопрос.

Вот проблема, которую я задаюлицом : мне будет предоставлен большой текст (например, 150 000 слов), а после этого серия фраз (каждая фраза содержит от 1 до 10 слов).Для каждой из этих фраз мне нужно найти слово, которое следует сразу за фразой в тексте, и вернуть ее.

Моя единственная идея до сих пор решить ее : создать структуру, которая содержит:

• текущее слово
• 3 слова, предшествовавшие этому слову
• слово, которое следует за

Тогда я бы проанализировал текстсоздание одной структуры для каждого слова и сохранение всех этих структур в хеш-таблице.По мере появления каждой фразы я буду искать в хэш-таблице последнее слово этой фразы, проверять, совпадают ли предыдущие 3 слова, а затем возвращать следующее слово.Я верю, что возврата к 3 словам будет достаточно для однозначного определения фраз, но я мог бы увеличить это число.

Как вы думаете, это сработает?Вы знаете лучший способ?

Answer 1

Гораздо проще подход: пробежаться по тексту, сохраняя все n -граммы (подпоследовательности n слов) для 1 <= <em>n <= 10 вхэш-таблица или три.В этом случае извлечение является тривиальным, просто найдите <em>n -грамму в хеш-таблице или три.

В версии хеш-таблицы вы просто сохраните n -граммы как конкатенации строк слов с нормализованным пробелом между ними.

Проблема этого подхода заключается в том, что для хеш-таблицы вам потребуется до 45 * N записей, где N - количество слов в тексте.Однако поиск должен быть очень быстрым, и 150 000 слов - это достаточно маленький набор данных, чтобы это работало.

Answer 2

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

Можно рассмотреть две версии деревьев суффиксов:

• характер на основе
• на основе маркеров