algorithm - 最受欢迎的子串

Question

我正在尝试将大量短字符串解析为一些逻辑部分。这似乎是一个有趣的问题，有人可能已经解决了，但我找不到任何论文/解决方案(或者我可能正在尝试错误的关键字)。

字符串有 2-5 个部分。如果我用每个单词替换一个字母，说明它属于哪个“部分”/“部分”，这里将是它们的示例:

AAABB
AABBBBCC
AABBBBDD
AAACCDD
...

大多数“部分”只有 2-3 个单词长，并且在 ~10k 字符串中出现约 100-500 次完全相同的部分。这意味着，在 100 个字符串中有 AAA == "some text here"，在其他 100 个字符串中有 AAA == "some other text"。在一个字符串中，每种类型只能有一个部分(它们通常按顺序排列)。任何部分都没有有限的一组值，将来可能会出现新值。

问题是:如果我有足够的样本并且不想手动标记它们，我该如何检测这些部分？这个可以监督/确认，不是全自动的，所以一个概率列表就可以了。

我正在考虑简单地制作一个包含 2-5 个长单词 n-gram 的列表并找出概率，但这并没有考虑顺序(这可能会有帮助)。它还会检测到某些文本很常见，但如果我有一些特定的 2 个部分经常使用相同的值，则此方法将无法正常工作。假设我只有由 ABCD 组成的字符串，每行的值都相同:

ABC
ABD
ACD

仅进行 ngram 分析，我很有可能将 A 以及 AB、C 和 D 作为一个部分。在这种情况下，我想从结果中消除 AB，但在某种程度上不会不要将自己的部分分配给像“the”这样的词，并删除所有恰好包含“the”的较大部分。

是否有针对类似问题的已知解决方案？

Answer 1

Lempel-Ziv-Welch算法在识别常见子串方面非常有效，但它不会尝试对它们进行排名。它也不注意单词或行的边界。仍然可以将其用作获得所需内容的起点。