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++)
        {

        }
    }

如你所见,我一直在寻找正在进行的比赛.

有任何想法吗？

Answer 1

您应该研究Smith-Waterman 算法来进行本地字符串对齐。它是一种动态编程算法，可查找字符串中编辑距离较短的相似部分。

因此，如果您想尝试一下，这里是该算法的 php 实现。