有两个挑战：
A. Levenshtein distance的并行执行——而不是顺序循环
B. 比较次数：如果我们的源列表有 400 万个条目，理论上我们应该运行 16 万亿次 Levenstein 距离度量，这是不现实的，即使我们解决了第一个挑战。
为了使我对语言的使用更加清晰，以下是我们的定义
- 我们想要测量表达式之间的编辑距离。
- 每个表达式都有两个部分，父级 A 全名和父级 B 全名，用加号分隔
- 各部分的顺序很重要（即，如果表达式 1 的父级 A = 表达式 2 的父级 A 且父级 B 或表达式 1= 表达式 2 的父级 B，则两个表达式 (1, 2) 是相同的。如果父级表达式 1 的 A = 表达式 2 的父级 B 且表达式 1 的父级 B = 表达式 2 的父级 A)
- 部分（或全名）是一系列单词，由空格或破折号分隔，对应于一个人的名字和姓氏
- 我们假设一个部分中的最大单词数为 6（您的示例有 2 或 3 个单词的部分，我假设我们最多可以有 6 个）
部分中的单词顺序很重要（该部分始终是名字后面是姓氏，而不是姓氏在前，例如 Jack John 和 John Jack 是两个不同的人）。
- 有400万个表达方式
- 假定表达式仅包含英文字符。数字、空格、标点符号、破折号和任何非英文字符都可以忽略
- 我们假设简单匹配已经完成（如精确表达式匹配），并且我们不必搜索精确匹配
从技术上讲，目标是在 400 万个表达式列表中找到一系列匹配的表达式。如果两个表达式的 Levenstein 距离小于 2，则它们被视为匹配表达式。
实际上，我们创建了两个列表，它们是最初 400 万个表达式列表的精确副本。我们称之为左列表和右列表。在复制列表之前，每个表达式都会被分配一个表达式 id。
我们的目标是找到 Right 列表中与 Left 列表的条目的 Levenstein 距离小于 2 的条目，不包括相同的条目（相同的表达式 id）。
我建议采用两步法来分别解决这两个挑战。第一步将减少可能匹配表达式的列表，第二步将简化 Levenstein 距离测量，因为我们只查看非常接近的表达式。使用的技术是任何传统的数据库服务器，因为我们需要对数据集进行索引以提高性能。
挑战A
挑战 A 包括减少距离测量的数量。我们从最大值大约开始。 16万亿（400万的2次方），我们不应该超过几千万或几亿。
这里使用的技术包括在完整的表达式中搜索至少一个相似的单词。根据数据的分布方式，这将大大减少可能的匹配对的数量。或者，根据结果所需的准确性，我们还可以搜索具有至少两个相似单词或至少一半相似单词的对。
从技术上讲，我建议将表达式列表放在表格中。添加标识列以为每个表达式创建唯一的 ID，并创建 12 个字符列。然后解析表达式并将每个部分的每个单词放在单独的列中。这看起来像（我没有表示所有 12 列，但想法如下）：
|id | expression | sect_a_w_1 | sect_a_w_2 | sect_b_w_1 |sect_b_w_2 |
|1 | peter pan + marta steward | peter | pan | marta |steward |
虽然有空列（因为 12 个单词的表达很少），但这并不重要。
然后我们复制该表并在每个部分...列上创建一个索引。
我们运行 12 个连接来尝试查找相似的单词，例如
SELECT L.id, R.id
FROM left table L JOIN right table T
ON L.sect_a_w_1 = R.sect_a_w_1
AND L.id <> R.id
我们收集 12 个临时表中的输出，并对这 12 个表运行联合查询，以获取所有表达式的简短列表，这些表达式具有至少一个相同单词的潜在匹配表达式。这是我们的挑战 A 的解决方案。我们现在有一个最可能匹配对的简短列表。该列表将包含数百万条记录（左右条目对），但不是数十亿条。
挑战B
挑战 B 的目标是批量处理简化的 Levenstein 距离（而不是循环运行）。
首先，我们应该就什么是简化的莱文斯坦距离达成一致。
首先我们同意两个表达式的levenstein距离是两个表达式中具有相同索引的所有单词的levenstein距离之和。我的意思是两个表达式的 Levenstein 距离是它们的两个第一个单词的距离，加上它们的两个第二个单词的距离，等等。
其次，我们需要发明一个简化的莱文斯坦距离。我建议使用 n-gram 方法，仅包含 2 个字符的克，其索引绝对差小于 2 。
例如peter和pieter之间的距离计算如下
Peter
1 = pe
2 = et
3 = te
4 = er
5 = r_
Pieter
1 = pi
2 = ie
3 = et
4 = te
5 = er
6 = r_
Peter 和 Pieter 有 4 个常见的 2-gram，索引绝对差小于 2 'et'、'te'、'er'、'r_'。两个单词中最大的一个有 6 个可能的 2-gram，则距离为 6-4 = 2 - Levenstein 距离也将为 2，因为有 1 个“eter”移动和一个字母插入“i”。
这是一个近似值，并不适用于所有情况，但我认为在我们的情况下它会工作得很好。如果我们对结果的质量不满意，我们可以尝试使用 3 克或 4 克或允许大于 2 克的序列差异。但其想法是每对执行的计算量比传统的 Levenstein 算法要少得多。
然后我们需要将其转化为技术解决方案。我之前所做的如下：
首先隔离单词：由于我们只需要测量单词之间的距离，然后将每个表达式的这些距离相加，我们可以通过在单词列表上运行不同的选择来进一步减少计算次数（我们已经准备好了单词列表）上一节中的单词）。
这种方法需要一个映射表来跟踪表达式id、部分id、单词id和单词的单词序列号，以便可以在过程结束时计算原始表达式距离。
然后我们得到一个更短的新列表，并且包含与 2 克距离度量相关的所有单词的交叉连接。
然后我们想要批量处理这个 2-gram 距离测量，我建议在 SQL 连接中进行。这需要一个预处理步骤，其中包括创建一个新的临时表，将每个 2-gram 存储在单独的行中，并跟踪单词 Id、单词序列和部分类型
从技术上讲，这是通过使用一系列（或循环）子字符串选择对单词列表进行切片来完成的，如下所示（假设单词列表表 - 有两个副本，一个左副本和一个右副本 - 包含 2 列 word_id 和 word）：
INSERT INTO left_gram_table (word_id, gram_seq, gram)
SELECT word_id, 1 AS gram_seq, SUBSTRING(word,1,2) AS gram
FROM left_word_table
进而
INSERT INTO left_gram_table (word_id, gram_seq, gram)
SELECT word_id, 2 AS gram_seq, SUBSTRING(word,2,2) AS gram
FROM left_word_table
Etc.
使“steward”看起来像这样的东西（假设单词 id 是 152）
| pk | word_id | gram_seq | gram |
| 1 | 152 | 1 | st |
| 2 | 152 | 2 | te |
| 3 | 152 | 3 | ew |
| 4 | 152 | 4 | wa |
| 5 | 152 | 5 | ar |
| 6 | 152 | 6 | rd |
| 7 | 152 | 7 | d_ |
不要忘记在 word_id、gram 和 gram_seq 列上创建索引，距离可以通过左右 gram 列表的连接来计算，其中 ON 看起来像
ON L.gram = R.gram
AND ABS(L.gram_seq + R.gram_seq)< 2
AND L.word_id <> R.word_id
距离是两个单词中最长的单词的长度减去匹配克的数量。 SQL 进行此类查询的速度非常快，我认为一台具有 8 GB RAM 的简单计算机可以在合理的时间范围内轻松执行数亿行。
然后只需连接映射表即可计算每个表达式中单词到单词的距离之和，从而得到总的表达式到表达式的距离。
