一种计算两个词之间编辑距离的算法
An algorithm for computing the edit-distance between two words
我正在尝试编写 Python 代码，将单词作为输入（例如书），并输出具有相似度得分的最相似单词。
我尝试过不同的现成编辑距离算法，如余弦、Levenshtein 和其他算法，但这些算法无法区分差异程度。例如，(book, bouk) 和 (book, bo0k)。我正在寻找一种可以为这两个示例给出不同分数的算法。我正在考虑使用 fastText 或 BPE，但它们使用的是余弦距离。
有什么算法可以解决这个问题吗？
问题是 "bo0k" 和 "bouk" 都与 "book" 有一个不同的字符，没有其他指标可以让您区分它们。
您需要做的是更改评分：不是将不同的字符计为 1 的编辑距离，如果它是不同的字符 class（即数字而不是字母）。这样你的例子就会得到不同的分数。
不过，您可能还需要调整其他分数，以便替换/插入/删除仍然一致。
这是一个非常有趣的问题 - 可能有很多可能的答案。您可以添加二元语法分析（n-gram）来对字母在典型单词中相互关联的可能性进行排序。
假设您的系统没有 "know" 目标词，但有人键入 "bouk"。然后它分析所有的二元组：
博，欧，英国
或八卦
布，乌克
我在这里猜测 "bo"、"ou"、"bou" 会得分很高，因为它们很常见，但 "uk" 和 "ouk" 不会可能是英文的。所以这可以简单地有一个 3/5 的分数，但实际上每个三元组都有自己的频率分数（概率），所以建议词的总数可以相当精确。
然后将其与 "bo0k" 进行比较，您会看到所有双字母组：
bo, o0, 0k
或八卦
bo0,o0k
现在你可以看到只有"bo"在这里得分高。所有其他的都不会在一个共同的 n-gram 语料库中找到。所以这个词的可能性得分比 "bouk" 低得多，例如1/5 与 "bouk".
的 3/5 相比
解决方案大致分为三个部分：
您需要该语言的既定 n-gram 频率语料库。例如，我发现的这个随机博客讨论了：https://blogs.sas.com/content/iml/2014/09/26/bigrams.html
然后您需要将输入的单词处理（标记化和扫描）为 n-gram，然后在语料库中查找它们的频率。你可以使用像 SK Learn 这样的东西，
然后您可以按照自己喜欢的方式对各部分进行加总，得出单词的总分。
请注意，您可能会发现自然语言的大多数分词器和 n-gram 处理都围绕 单词关系 而不是单词中的字母。很容易迷失在这一点上，因为图书馆专注于词语法的事实往往没有被明确提及，因为它是最常见的。我以前注意到过，但是 n-gram 也用于各种其他数据集（时间序列、音乐、任何序列）这个问题确实讨论了如何将 SK Learn 的向量化器转换为字母-gram，但我'我自己没有尝试过：
我有第二个想法，在这种情况下使用 "domain knowledge"，有人在键盘上打字。它没有直接回答您的问题，但说明可能有完全不同的方法来实现最终目标（您没有直接描述 - 即用户界面提供拼写检查选项？）。
我曾经在 uni 写过一个算法，它使用键盘布局映射（作为拼写检查器中的一种策略），迭代所有周围的键，在找不到单词时提出 "fat fingering" 更正在字典里。
例如，O 被 I90PLK 包围，I 被 U89OK 或 U89OKJ 包围。
因此，您可以通过将每个字母替换为周围邻居的所有组合来改变每个输入单词。您最终会得到很多组合，但其中大部分完全是假词。其中之一可能与字典单词完美匹配。
因此，您需要做的就是生成所有可能的拼写错误邻居，然后简单地查找突变体中的所有词典单词，这应该是一个高效的查询。
例如对于 bo0k
bo0k
vo0k
go0k
ho0k
no0k
_o0k
bi0k
b90k
b00k
bp0k
bl0k
bk0k
bo9k
bo0k
bo-k
bopk
book - bingo!
boik
bo0j
bo0u
bo0i
bo0o
bo0l
bo0,
bo0m
这里可以看到整套基本错字突变词只有一个字典词
所以这不使用任何相似性算法，但在键盘打字错误的情况下，它可以找到更正。您甚至可以记录这些建议的用户 "acceptance" 并形成您自己的修正概率语料库。我猜很多拼写错误都很常见且一致。
显然这不包括拼写错误，尽管根据具有特定怪癖和困难的自然语言可以采用类似的领域知识方法。
我正在尝试编写 Python 代码，将单词作为输入（例如书），并输出具有相似度得分的最相似单词。
我尝试过不同的现成编辑距离算法，如余弦、Levenshtein 和其他算法，但这些算法无法区分差异程度。例如，(book, bouk) 和 (book, bo0k)。我正在寻找一种可以为这两个示例给出不同分数的算法。我正在考虑使用 fastText 或 BPE，但它们使用的是余弦距离。
有什么算法可以解决这个问题吗？
问题是 "bo0k" 和 "bouk" 都与 "book" 有一个不同的字符，没有其他指标可以让您区分它们。
您需要做的是更改评分：不是将不同的字符计为 1 的编辑距离，如果它是不同的字符 class（即数字而不是字母）。这样你的例子就会得到不同的分数。
不过，您可能还需要调整其他分数，以便替换/插入/删除仍然一致。
这是一个非常有趣的问题 - 可能有很多可能的答案。您可以添加二元语法分析（n-gram）来对字母在典型单词中相互关联的可能性进行排序。
假设您的系统没有 "know" 目标词，但有人键入 "bouk"。然后它分析所有的二元组：
博，欧，英国
或八卦
布，乌克
我在这里猜测 "bo"、"ou"、"bou" 会得分很高，因为它们很常见，但 "uk" 和 "ouk" 不会可能是英文的。所以这可以简单地有一个 3/5 的分数，但实际上每个三元组都有自己的频率分数（概率），所以建议词的总数可以相当精确。
然后将其与 "bo0k" 进行比较，您会看到所有双字母组：
bo, o0, 0k
或八卦
bo0,o0k
现在你可以看到只有"bo"在这里得分高。所有其他的都不会在一个共同的 n-gram 语料库中找到。所以这个词的可能性得分比 "bouk" 低得多，例如1/5 与 "bouk".
的 3/5 相比解决方案大致分为三个部分：
您需要该语言的既定 n-gram 频率语料库。例如，我发现的这个随机博客讨论了：https://blogs.sas.com/content/iml/2014/09/26/bigrams.html
然后您需要将输入的单词处理（标记化和扫描）为 n-gram，然后在语料库中查找它们的频率。你可以使用像 SK Learn 这样的东西，
然后您可以按照自己喜欢的方式对各部分进行加总，得出单词的总分。
请注意，您可能会发现自然语言的大多数分词器和 n-gram 处理都围绕 单词关系 而不是单词中的字母。很容易迷失在这一点上，因为图书馆专注于词语法的事实往往没有被明确提及，因为它是最常见的。我以前注意到过，但是 n-gram 也用于各种其他数据集（时间序列、音乐、任何序列）这个问题确实讨论了如何将 SK Learn 的向量化器转换为字母-gram，但我'我自己没有尝试过：
我有第二个想法，在这种情况下使用 "domain knowledge"，有人在键盘上打字。它没有直接回答您的问题，但说明可能有完全不同的方法来实现最终目标（您没有直接描述 - 即用户界面提供拼写检查选项？）。
我曾经在 uni 写过一个算法，它使用键盘布局映射（作为拼写检查器中的一种策略），迭代所有周围的键，在找不到单词时提出 "fat fingering" 更正在字典里。
例如，O 被 I90PLK 包围，I 被 U89OK 或 U89OKJ 包围。
因此，您可以通过将每个字母替换为周围邻居的所有组合来改变每个输入单词。您最终会得到很多组合，但其中大部分完全是假词。其中之一可能与字典单词完美匹配。
因此，您需要做的就是生成所有可能的拼写错误邻居，然后简单地查找突变体中的所有词典单词，这应该是一个高效的查询。
例如对于 bo0k
bo0k
vo0k
go0k
ho0k
no0k
_o0k
bi0k
b90k
b00k
bp0k
bl0k
bk0k
bo9k
bo0k
bo-k
bopk
book - bingo!
boik
bo0j
bo0u
bo0i
bo0o
bo0l
bo0,
bo0m
这里可以看到整套基本错字突变词只有一个字典词
所以这不使用任何相似性算法，但在键盘打字错误的情况下，它可以找到更正。您甚至可以记录这些建议的用户 "acceptance" 并形成您自己的修正概率语料库。我猜很多拼写错误都很常见且一致。
显然这不包括拼写错误，尽管根据具有特定怪癖和困难的自然语言可以采用类似的领域知识方法。