基于PHP中一组形式相似的字母的拼写修正改进

Question

我正在为非英语语言开发一个用于OCR输出的拼写校正系统。我用非常大的字典来检查拼写错误并给出建议。

大多数拼写错误是因为字母的形式相似。例如ـجـ、ـچـ、ـحـ、ـخـ或غ、ع等。这些字母也以英文存在，例如I、l和u、v、y。

拼写检查系统为我们要检查的一个单词提供了一些建议。例如，如果我们输入voga，它会建议使用以下单词：

• volga
• boga
• yoga
• toga

既然voga的长度是4，那么我们只保留4个字母的建议.现在，由于OCR引擎可以将v检测为y (因为它们的形式相似)，所以我们将选择yoga作为voga输出的最佳建议。

在我们的语言中，这种选择是非常有效的。例如，如果我们输入مدپر，这些单词将被建议：

• مدارا
• مدار
• مدیر
• مراد

根据我们的集合(在本例中：ـبـ、ـپـ、ـیـ和ز、ر、ژ和ذ、د和مـ、فـ、قـ)和word的长度，مدیر将是مدپر的最佳选择。

我通常在PHP脚本语言中实现这个函数的方法是保持相同长度的单词，然后通过替换所有集合(如مدپر、فدپر、قدپر和مذپر、فذپر、قذپر等)来创建拼写错误的单词的所有可能组合，然后在建议列表中搜索相同的单词。但是这种实现方法真的很慢(特别是在一个大的上下文中)，使得它几乎毫无用处。

在PHP中实现这种函数的最佳方法或算法是什么？

更新：

对生成建议列表的引擎进行优化，通常在建议列表中包含正确的单词。问题是，我的系统必须选择其中一个建议作为正确的词，没有任何人工智能。因此，我认为这种方法在我的语言中是很好的，因为有许多字母具有相似的形式，这就是为什么OCR引擎通常错误地检测单词的原因。但如果有更好的方法，欢迎您提出建议。

Answer 1

我仍然认为这个问题太宽泛，不能在这里提出。在我看来，你似乎不知道该如何做，所以不应该要求PHP解决方案。在我看来，这个问题首先是关于算法解决方案，而不是关于编程或实现。我相信有许多不同的解决方案，而且由于我们几年前在这个领域做了一项科学研究，我将提出一个解决方案，让你得到一些线索，你可以这样做。

假设您有一个"OCR单词“，它是无效的，您希望从有效单词字典中选择最佳的有效词来替换它。

1. 从标准建议算法开始。所以你有几个候选词。
2. 现在计算这些单词到OCR单词的“距离”。
3. 使用最小计算距离的候选人。

现在的问题是如何计算两个单词的距离。您可以从Hamming距离开始--但是这个经典算法对于您的情况还不够好，而且它不会比您从第一步获得的内容做得更多，所以您需要做一些更适合您的事情。简单地说，你想给一些类似的符号/字母奖金。我们用模糊自动机来解决同样的DNA分析问题。在这里编写完整的算法太长了，所以如果需要更多信息，请查看我们的论文。(链接转到researchgate存储库。)

您也可以完全跳过步骤1，创建一个具有相似之处的全局搜索系统，这在我们的文章中也有描述。我将投票赞成这一全球办法。