我有主要包含项目列表的文本文档。
每个项目是一组来自不同类型的多个标记：名字、姓氏、出生日期、电话号码、城市、职业等。标记是一组单词。
项目可以位于多行。
文档中的项目具有大致相同的标记语法，但它们不一定必须完全相同。
它们可能是项目之间以及项目内部的一些更多/更少的标记。
FirstName LastName BirthDate PhoneNumber
Occupation City
FirstName LastName BirthDate PhoneNumber PhoneNumber
Occupation City
FirstName LastName BirthDate PhoneNumber
Occupation UnrecognizedToken
FirstName LastName PhoneNumber
Occupation City
FirstName LastName BirthDate PhoneNumber
City Occupation
目标是识别使用的语法，例如
Occupation City
最后确定所有项目，即使它们不完全匹配。
为了保持简短易读，让我们使用一些别名 A、B、C、D、... 来指定这些标记类型。
例如
A B C
D F
A B C
D E F
F
A B C
D E E F
A C B
D E F
A B D C
D E F
A B C
D E F G
在这里我们可以看到Item语法是
A B C
D E F
因为它是最匹配序列的那个。
语法（令牌类型和顺序）可能因一个文档而异。例如，另一个文档可能有该列表
D A
D A
D
D A
B
D A
目标是在没有先验知识的情况下找出该语法。
从现在开始，新行也被视为令牌。然后可以将文档表示为一维标记序列：
这里重复的序列将是A B C B因为它是产生最少冲突的令牌。
让我们把它复杂一点。从现在开始，每个令牌都没有确定的类型。在现实世界中，我们并不总是 100% 确定某个代币的类型。相反，我们给它一个具有某种类型的概率。
A 0.2 A 0.0 A 0.1
B 0.5 B 0.5 B 0.9 etc.
C 0.0 C 0.0 C 0.0
D 0.3 D 0.5 D 0.0
这是我想要实现的抽象图形：
考虑的解决方案 A：标记块的卷积
该解决方案包括应用带有多个令牌补丁的卷积，并采用产生最少冲突的那个。
这里的难点是找到潜在的补丁来沿着观察序列滚动。这个想法很少，但没有什么非常令人满意的：
建立代币之间转换的马尔可夫模型缺点：由于马尔可夫模型没有记忆，我们会失去转移的顺序。例如，如果重复序列是A B C B D，我们就失去了 A->B 出现在 C->B 之前的事实。
这似乎在生物学中被广泛使用，以分析 DNA/RNA 中的核碱基 (GTAC)。缺点：后缀树有利于精确标记（例如字符）的精确匹配。我们既没有准确的序列，也没有准确的记号。
蛮力尝试每种尺寸的每种组合。实际上可以工作，但需要一些（长（长））时间。
考虑的解决方案 B：建立后缀的 Levenshtein 距离表
直觉是，在计算每个后缀到每个后缀的距离时，可能存在一些局部最小距离。
距离函数是 Levenshtein 距离，但我们将来可以对其进行自定义，以便考虑属于特定类型的概率，而不是为每个令牌设置一个固定类型。
为了在演示中保持简单，我们将使用固定类型的令牌，并使用经典的 Levenshtein 来计算令牌之间的距离。
例如让我们输入序列ABCGDEFGH ABCDEFGH ABCDNEFGH。
我们计算每个后缀与每个后缀的距离（裁剪为相等大小）：
for i = 0 to sequence.lengh
for j = i to sequence.lengh
# Create the suffixes
suffixA = sequence.substr(i)
suffixB = sequence.substr(j)
# Make the suffixes the same size
chunkLen = Math.min(suffixA.length, suffixB.length)
suffixA = suffixA.substr(0, chunkLen)
suffixB = suffixB.substr(0, chunkLen)
# Compute the distance
distance[i][j] = LevenshteinDistance(suffixA, suffixB)
我们得到例如以下结果（白色是小距离，黑色是大距离）：
现在，很明显，任何与自身相比的后缀都将具有零距离。但是我们对后缀（完全或部分）匹配本身不感兴趣，所以我们裁剪了那部分。
由于后缀被裁剪为相同的大小，比较长字符串总是比比较小字符串产生更大的距离。
我们需要通过从右侧 (+P) 开始向左侧线性淡出的平滑惩罚来补偿这一点。
我还不确定如何选择适合所有情况的良好惩罚函数。
在这里，我们在最右边应用 (+P=6) 惩罚，向左淡出到 0。
现在我们可以清楚地看到两条清晰的对角线出现了。该序列中有 3 个项目（项目 1、项目 2、项目 3）。最长的线表示 Item1 与 Item2 和 Item2 与 Item3 之间的匹配。第二长表示 Item1 与 Item3 之间的匹配。
现在我不确定利用这些数据的最佳方法。是否像取最高对角线一样简单？
让我们假设它是。
让我们计算从每个标记开始的对角线的平均值。我们可以在下图中看到结果（矩阵下方的向量）：
显然有 3 个局部最小值，它们与每个项目的开头相匹配。看起来棒极了！
现在让我们在序列中添加更多的缺陷：
ABCGDEFGH ABCDEFGH TROLL ABCDEFGH
很明显，我们的对角线平均向量已经搞砸了，我们不能再利用它了……
我的假设是，这可以通过自定义距离函数（而不是 Levenshtein）来解决，其中插入整个块可能不会受到太多惩罚。那是我不确定的。
结论
探索的基于卷积的解决方案似乎都不适合我们的问题。
基于 Levenshtein 距离的解决方案似乎很有希望，特别是因为它与基于概率的类型令牌兼容。但我还不确定如何利用它的结果。
如果您有相关领域的经验，并给我们一些好的提示，或者其他需要探索的技术，我将非常感激。非常感谢您提前。