python - 拼写检查遗传算法的实现

Question

我想实现拼写检查器，它将检查文本文件中的拼写并输出错误和更正。我想使用 python 创建它。

但是，主要的是我想用遗传算法来实现它。如何实现拼写检查器的遗传算法？

Answer 1

不要指望我在这里的想法是完美的或最佳的，但如果你决定走这条路，这对你来说可能是一个很好的起点。不过，遗传算法可能不是拼写检查器的最佳选择。

对于遗传算法，您需要有一个起始种群，一种将基因传递给“下一代”（交叉）的方法，一种创建突变的明确方法，以及一种选择哪些基因传递给下一代的方法（又名适应度函数）。当然，除此之外，您还需要一个语料库。您可以尝试使用 dictionary.com API，如果它有任何好处（我从未使用过）http://www.programmableweb.com/api/dictionary.com。

对于起始人口，您有一个可怕的问题，即您的起始人口将是数千个完全相同的单词（即 ['hello']*1000）。从这里你可以检查它是否是一个单词，然后如果它只是返回 True （因为检查那里的语法和他们的 vs 他们会很痛苦）。

首先，您需要完全依靠突变来获得多样性，因此如果是较早的一代，可能会使突变更有可能发生，而一旦多样性增加，突变的机会就会减少。突变可以是任何一种：在某处插入一个随机字母，在某处删除一个字母，在某处更改一个字母，做不止一个。

对于您的适应度函数，您最好的选择是使用序列比对算法。请参阅：http ://en.wikipedia.org/wiki/Sequence_alignment 。如果你真的想进步，试着为你的人口中的每个单词创建语音拼写，看看它们是否匹配语料库中的任何内容，并在此基础上增加分数（即，尽管发音相同）。我不能声称对此一无所知。请记住，所有这些都会严重降低您的应用程序速度，因此请记住这一点。最好将您的人口限制在 1000-2000 人之间。

对于您的交叉，您应该采取一些样本（早期您可能需要使用轮盘赌来选择最适合的，但稍后您可以使用锦标赛来提高速度）。同样，您可以使用每个“父级”之间的序列比对，然后决定从每个父级中提取哪个字母（即 soeed 与 s_eeo 可以是 soeed、seed、seeo 或 soeeo）。

不要将此视为专家解决方案，而且我只考虑了几分钟，但如果您决定使用遗传算法，这可能是一个好的开始。