8

levenshteinPHP の関数は、最大長が255の文字列で機能します。PHPで文の類似度スコアを計算するための適切な代替手段は何ですか。

基本的に私は文章のデータベースを持っています、そして私はおおよその重複を見つけたいです。 similar_text関数は私に期待される結果を与えていません。以下のような類似の文を検出するための最も簡単な方法は何ですか？

$ss="Jack is a very nice boy, isn't he?";
$pp="jack is a very nice boy is he";

$ss=strtolower($ss);  // convert to lower case as we dont care about case
$pp=strtolower($pp);

$score=similar_text($ss, $pp);
echo "$score %\n";  // Outputs just 29 %

$score=levenshtein ( $ss, $pp );
echo "$score\n";  // Outputs '5', which indicates they are very similar. But, it does not work for more than 255 chars :(
4

3 に答える 3

10

levenshteinアルゴリズムの時間計算量は です。O(n*m)ここで、nとmは 2 つの入力文字列の長さです。これは非常にコストがかかり、長い文字列の距離を計算するには長い時間がかかります。

文全体については、diff代わりにアルゴリズムを使用することをお勧めします。例を参照してください: PHP で 2 つの文字列の違いを強調する

そうは言っても、PHP はsimilar_textさらに複雑な関数 ( O(max(n,m)**3)) を提供しますが、より長い文字列で動作するようです。

于 2011-02-23T15:15:01.913 に答える
3

Smith Waterman Gotohが文の比較に最適なアルゴリズムであることがわかりました。詳細については、この回答を参照してください。PHP コードの例を次に示します。

class SmithWatermanGotoh 
{
    private $gapValue;
    private $substitution;

    /**
     * Constructs a new Smith Waterman metric.
     * 
     * @param gapValue
     *            a non-positive gap penalty
     * @param substitution
     *            a substitution function
     */
    public function __construct($gapValue=-0.5, 
                $substitution=null) 
    {
        if($gapValue > 0.0) throw new Exception("gapValue must be <= 0");
        //if(empty($substitution)) throw new Exception("substitution is required");
        if (empty($substitution)) $this->substitution = new SmithWatermanMatchMismatch(1.0, -2.0);
        else $this->substitution = $substitution;
        $this->gapValue = $gapValue;
    }

    public function compare($a, $b) 
    {
        if (empty($a) && empty($b)) {
            return 1.0;
        }

        if (empty($a) || empty($b)) {
            return 0.0;
        }

        $maxDistance = min(mb_strlen($a), mb_strlen($b))
                * max($this->substitution->max(), $this->gapValue);
        return $this->smithWatermanGotoh($a, $b) / $maxDistance;
    }

    private function smithWatermanGotoh($s, $t) 
    {   
        $v0 = [];
        $v1 = [];
        $t_len = mb_strlen($t);
        $max = $v0[0] = max(0, $this->gapValue, $this->substitution->compare($s, 0, $t, 0));

        for ($j = 1; $j < $t_len; $j++) {
            $v0[$j] = max(0, $v0[$j - 1] + $this->gapValue,
                    $this->substitution->compare($s, 0, $t, $j));

            $max = max($max, $v0[$j]);
        }

        // Find max
        for ($i = 1; $i < mb_strlen($s); $i++) {
            $v1[0] = max(0, $v0[0] + $this->gapValue, $this->substitution->compare($s, $i, $t, 0));

            $max = max($max, $v1[0]);

            for ($j = 1; $j < $t_len; $j++) {
                $v1[$j] = max(0, $v0[$j] + $this->gapValue, $v1[$j - 1] + $this->gapValue,
                        $v0[$j - 1] + $this->substitution->compare($s, $i, $t, $j));

                $max = max($max, $v1[$j]);
            }

            for ($j = 0; $j < $t_len; $j++) {
                $v0[$j] = $v1[$j];
            }
        }

        return $max;
    }
}

class SmithWatermanMatchMismatch
{
    private $matchValue;
    private $mismatchValue;

    /**
     * Constructs a new match-mismatch substitution function. When two
     * characters are equal a score of <code>matchValue</code> is assigned. In
     * case of a mismatch a score of <code>mismatchValue</code>. The
     * <code>matchValue</code> must be strictly greater then
     * <code>mismatchValue</code>
     * 
     * @param matchValue
     *            value when characters are equal
     * @param mismatchValue
     *            value when characters are not equal
     */
    public function __construct($matchValue, $mismatchValue) {
        if($matchValue <= $mismatchValue) throw new Exception("matchValue must be > matchValue");

        $this->matchValue = $matchValue;
        $this->mismatchValue = $mismatchValue;
    }

    public function compare($a, $aIndex, $b, $bIndex) {
        return ($a[$aIndex] === $b[$bIndex] ? $this->matchValue
                : $this->mismatchValue);
    }

    public function max() {
        return $this->matchValue;
    }

    public function min() {
        return $this->mismatchValue;
    }
}

$str1 = "Jack is a very nice boy, isn't he?";
$str2 = "jack is a very nice boy is he";
$o = new SmithWatermanGotoh();
echo $o->compare($str1, $str2);
于 2016-07-07T01:37:42.427 に答える
2

similar_textを使用してみてください。
20,000文字以上（3〜5秒）でかなり遅くなる可能性がありますが、文のみを使用して言及した例では、その使用法で問題なく機能します.

注意すべきことの 1 つは、異なるサイズの文字列を比較する場合、100% にはならないことです。たとえば、"he" と "head" を比較すると、50% しか一致しません。

于 2011-02-23T15:17:59.343 に答える