基于 PHP 中具有相似形式的一组字母的拼写校正改进
Spell correction improvement based on a set of letters with similar forms in PHP
我正在开发一个适用于 OCR 输出的非英语拼写校正系统。我使用非常大的词典来检查拼写错误并提供建议。
大多数拼写错误是因为字母的形式相似。例如 ـجـ
, ـچـ
, ـحـ
, ـخـ
或 غ
, ع
等。这些字母也存在于英文中,例如 I
, l
和 u
, v
, y
.
拼写检查系统对我们要检查的单词给出了一些建议。例如,如果我们输入 voga
它会建议这些词:
volga
boga
yoga
toga
由于 voga
的长度是 4,那么我们将只保留 4 个字母的建议。现在因为 OCR 引擎可以将 v
检测为 y
(因为它们的形式相似),我们将选择 yoga
作为 voga
作为 OCR 输出的最佳建议。
在我们的语言中,这种select离子非常有效。比如我们输入مدپر
,就会提示这些词:
مدارا
مدار
مدیر
مراد
基于我们的集合(在此示例中:ـبـ
、ـپـ
、ـیـ
和 ز
、ر
、ژ
和ذ
, د
和 مـ
, فـ
, قـ
) 和单词的长度,مدیر
将是 مدپر
的最佳选择。
我通常在 PHP 脚本语言中实现此功能的方式是让建议的单词保持相同的长度,然后通过替换所有集合(如 مدپر
、فدپر
、قدپر
,然后是 مذپر
、فذپر
、قذپر
等等),然后在建议列表中搜索相同的词。但是这种实现方法真的很慢(特别是在大上下文中)并且几乎没有用。
在PHP中实现这种功能的最佳方法或算法是什么?
更新:
生成建议列表的引擎经过优化,通常会在建议列表中包含正确的单词。问题是我的系统必须 select 建议之一作为正确的单词,而没有任何人工智能。所以我认为这种方法在我的语言中很好,因为有很多字母具有相似形式的集合,这就是为什么 OCR 引擎通常会错误地检测到单词。但如果有更好的方法,欢迎大家提出。
我仍然认为这个问题太宽泛了,不能在这里问。在我看来你仍然不知道如何去做,所以你不应该要求 PHP 解决方案。在我看来,这个问题首先是关于算法解决方案的,而不是关于编程或实现的。我相信存在许多不同的解决方案,并且由于我们几年前在该领域进行了科学研究,所以我将提出一个解决方案,让您了解如何做到这一点。
假设您有一个 "OCR word" 是无效的,您想要 select 最有效的词从您的有效词词典中替换它。
从标准建议算法开始。这样你就得到了几个候选词。
现在计算"distance"这些词到OCR词
使用计算距离最小的候选项。
现在的问题是如何计算两个单词的距离。如果您需要更多信息,可以从 Hamming distance - but this classic algorithm is not good enough for your situation and it will not do more than what you already have got from step 1, so you need to make something more suitable for you. Simply said you want to give some bonus for similar symbols/letters. We used a fuzzy automata to solve the very same situation for DNA analysis. It would be too long to write complete algorithm here, so please look at our paper 开始。 (link 转到 researchgate 存储库。)
你也可以完全跳过第1步,创建一个全局搜索系统来搜索具有相似性的相似词,这在我们的论文中也有描述。我会投票支持这种全球方法。
我正在开发一个适用于 OCR 输出的非英语拼写校正系统。我使用非常大的词典来检查拼写错误并提供建议。
大多数拼写错误是因为字母的形式相似。例如 ـجـ
, ـچـ
, ـحـ
, ـخـ
或 غ
, ع
等。这些字母也存在于英文中,例如 I
, l
和 u
, v
, y
.
拼写检查系统对我们要检查的单词给出了一些建议。例如,如果我们输入 voga
它会建议这些词:
volga
boga
yoga
toga
由于 voga
的长度是 4,那么我们将只保留 4 个字母的建议。现在因为 OCR 引擎可以将 v
检测为 y
(因为它们的形式相似),我们将选择 yoga
作为 voga
作为 OCR 输出的最佳建议。
在我们的语言中,这种select离子非常有效。比如我们输入مدپر
,就会提示这些词:
مدارا
مدار
مدیر
مراد
基于我们的集合(在此示例中:ـبـ
、ـپـ
、ـیـ
和 ز
、ر
、ژ
和ذ
, د
和 مـ
, فـ
, قـ
) 和单词的长度,مدیر
将是 مدپر
的最佳选择。
我通常在 PHP 脚本语言中实现此功能的方式是让建议的单词保持相同的长度,然后通过替换所有集合(如 مدپر
、فدپر
、قدپر
,然后是 مذپر
、فذپر
、قذپر
等等),然后在建议列表中搜索相同的词。但是这种实现方法真的很慢(特别是在大上下文中)并且几乎没有用。
在PHP中实现这种功能的最佳方法或算法是什么?
更新:
生成建议列表的引擎经过优化,通常会在建议列表中包含正确的单词。问题是我的系统必须 select 建议之一作为正确的单词,而没有任何人工智能。所以我认为这种方法在我的语言中很好,因为有很多字母具有相似形式的集合,这就是为什么 OCR 引擎通常会错误地检测到单词。但如果有更好的方法,欢迎大家提出。
我仍然认为这个问题太宽泛了,不能在这里问。在我看来你仍然不知道如何去做,所以你不应该要求 PHP 解决方案。在我看来,这个问题首先是关于算法解决方案的,而不是关于编程或实现的。我相信存在许多不同的解决方案,并且由于我们几年前在该领域进行了科学研究,所以我将提出一个解决方案,让您了解如何做到这一点。
假设您有一个 "OCR word" 是无效的,您想要 select 最有效的词从您的有效词词典中替换它。
从标准建议算法开始。这样你就得到了几个候选词。
现在计算"distance"这些词到OCR词
使用计算距离最小的候选项。
现在的问题是如何计算两个单词的距离。如果您需要更多信息,可以从 Hamming distance - but this classic algorithm is not good enough for your situation and it will not do more than what you already have got from step 1, so you need to make something more suitable for you. Simply said you want to give some bonus for similar symbols/letters. We used a fuzzy automata to solve the very same situation for DNA analysis. It would be too long to write complete algorithm here, so please look at our paper 开始。 (link 转到 researchgate 存储库。)
你也可以完全跳过第1步,创建一个全局搜索系统来搜索具有相似性的相似词,这在我们的论文中也有描述。我会投票支持这种全球方法。