algorithm - 什么算法可以将字符组合成单词？

Question

我有一些由一些糟糕的 OCR 软件生成的文本。

输出包含单词和空格分隔字符的混合，这些字符应该被分组到单词中。例如，

Expr e s s i o n Syntax
S u m m a r y o f T e r minology 

应该是

Expression Syntax
Summary of Terminology 

什么算法可以将字符组合成单词？

如果我使用 Python、C#、Java、C 或 C++ 编程，哪些库提供了算法的实现？

谢谢。

Answer 1

最小方法:

1. 在您的输入中，删除任何单字母单词前的空格。以某种方式将创建的最终单词标记为其中的一部分(例如，使用不在输入中的符号作为前缀)。
2. 获取英语单词字典，从最长到最短排序。
3. 对于输入中的每个标记单词，找到最长的匹配项并将其拆分为一个单词。重复原始“单词”中遗留下来的字符，直到什么都没有留下。 (如果没有匹配项，就不要管它。)

---

更复杂、矫枉过正的方法:

不带空格的单词拆分问题是常见的不带空格的语言(例如中文和日语)中的一个现实问题。我对日语很熟悉，所以我将主要引用它来说话。

典型的方法使用字典和序列模型。该模型经过训练以学习标签之间的转换属性——词性标记与字典相结合，用于计算不同潜在位置拆分单词的相对可能性。然后使用(例如)Viterbi 算法求解整个句子最可能的拆分序列。

如果您只是清理 OCR 数据，创建这样的系统几乎肯定是矫枉过正，但如果您有兴趣，它可能值得研究。

---

一个示例案例，其中更复杂的方法有效而简单的方法无效:

• 输入:Playforthefunofit
• 简单输出:Play forth efunofit ( forth 比 for 长)
• 复杂的输出:Play for the fun of it (forth efunofit 是低频 - 即不自然的过渡，而 for the 不是)

通过将常见的短词序列作为单元添加到字典中，您可以在某种程度上使用简单方法解决此问题。例如，添加 forthe作为字典单词，并在后处理步骤中将其拆分。

希望对您有所帮助 - 祝您好运!