从多个字符串中提取相似部分的PHP方法

Question

我正在尝试从多个字符串中提取相似的部分。

此举旨在尝试从标题页的多个OCR处理结果中提取书名。

仅适用于字符串开头，字符串结尾不需要修剪，可以保持原样。

例如，我的字符串可能是：

$title[0]='the history of the internet, expanded and revised';
$title[1]='the history of the internet';
$title[2]='published by xyz publisher the historv of the internot, expanded and';
$title[3]='history of the internet';

基本上，我想要修剪每个字符串，以便从最可能的起点开始。考虑到可能存在OCR错误（例如“historv”，“internot”），我认为最好从每个单词中取出字符数，这将为每个字符串（因此是多维数组）提供一个包含每个单词长度的数组。然后可以使用它来查找运行匹配并将字符串的开头修剪到最有可能的位置。

应该将字符串切割为：

$title[0]='the history of the internet, expanded and revised';
$title[1]='the history of the internet';
$title[2]='the historv of the internot, expanded and';
$title[3]='XXX history of the internet';

因此我需要能够识别“互联网的历史”（7 2 3 8）是匹配所有字符串的运行，而前面的“the”很可能是正确的，因为它出现在>50％的字符串中，因此每个字符串的开头都被修剪为“the”，并且在缺少“the”的字符串上添加相同长度的占位符。

到目前为止，我已经得到：

function CompareSimilarStrings($array)
    {
    $n=count($array);

    // Get length of each word in each string >
    for($run=0; $run<$n; $run++)
        {
        $temp=explode(' ',$array[$run]);
        foreach($temp as $key => $val)
         $len[$run][$key]=strlen($val);
        }

    for($run=0; $run<$n; $run++)
        {

        }
    }

你看，我卡在了找到正在运行的匹配项上。

有什么想法吗？

- Alasdair

---

OCR 会错过一个短单词或将字母误认为符号，这种情况难道不可能发生吗？这些“运行匹配”似乎并不适用于这种情况。 - erisco

它不会漏掉单词，但有时会把字母打错，所以我考虑使用每个单词中字母的数量。有时它会添加或删除一个字母，但脚本仍将匹配那些正确的字符串。 - Alasdair

我还想问一下：为什么标题不是“互联网的历史，扩展和...”？它与50%的样本很匹配，并且大部分子集与其余情况相匹配。是否有保证每个样本都包含完整的标题？这是我能想到的唯一明确的规则，可以使这个答案无效。 - erisco

没错，但我只想通过这个脚本切割字符串的开头。接下来，我有另外一个算法可以将它们合并成一个字符串，该算法会考虑到字符串结尾的部分。 - Alasdair

我明白了。如果你只关心最可能的开头，那么一串单词为什么很重要呢？这只需要逐个考虑每个单词，从左到右即可。如果我们首先看到“published”，我们会发现它并不是很受欢迎。当我们工作到“the”时，我们发现它非常受欢迎，而“history”的受欢迎程度则较低。因此，我们将选择“the”。然后，您的其他算法将担心结尾。您可能会注意到，如果真正的标题是“History of the published Internet”，那么这个算法会得出错误的结论，但根据什么标准呢？ - erisco

让我们在聊天中继续这个讨论：http://chat.stackoverflow.com/rooms/8152/discussion-between-erisco-and-alasdair - erisco

Answer 1

你应该了解Smith-Waterman算法，它是一种动态规划算法，用于查找字符串中类似的部分，这些部分具有较低的编辑距离。如果想尝试一下，这里有一个算法的PHP实现。

- gintas