Самые популярные подстроки

Question

Я пытаюсь разобрать большое количество коротких строк на некоторые логические части. Похоже, интересная проблема, которую кто-то уже мог решить, но я не могу найти какие-либо документы/решения (или, может быть, я пытаюсь использовать неправильные ключевые слова).

Строки имеют 2-5 частей. Если я заменить каждое слово на букву высказывании, которое «часть»/«раздела» она принадлежит, вот бы образец из них:

AAABB 
AABBBBCC 
AABBBBDD 
AAACCDD 
... 

Большинство «секций» только 2-3 слова длиной и существует ~ 100-500 вхождений одного и того же раздела в ~ 10k строк. Это означает, что есть AAA == «некоторый текст здесь» в 100 строках и AAA == «некоторый другой текст» в других 100. В одной строке может быть только один раздел каждого типа (и они обычно идут в порядке). В любом разделе нет ограниченного набора значений, и в будущем могут появиться новые значения.

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

Я думал о том, чтобы просто составить список из 2-5 длинных слов n-граммов и найти вероятность, но это не учитывает порядок (что может быть полезно). Он также обнаружит, что какой-то текст является общим, но если у меня есть некоторые конкретные 2 раздела с одинаковыми значениями, которые часто используются, этот метод не будет работать хорошо. Скажем, у меня есть только строки, которые состоят из ABCD с теми же значениями в каждой строке:

ABC 
ABD 
ACD 

Выполнения только Ngram анализа, я буду высокая вероятность, являющееся отделение, а также для AB, C и D Я хотел бы исключить AB из результатов в этом случае, но так, чтобы не назначать собственный раздел словам типа «the» и исключать все более крупные разделы, которые содержат «the».

Есть ли известные решения для подобных проблем?

Answer 1

Алгоритм Lempel-Ziv-Welch очень эффективен при определении общих подстрок, но он не пытается ранжировать их. Он также не обращает внимания на границы слов или строк. По-прежнему возможно использовать его в качестве отправной точки, чтобы получить то, что вам нужно.