使用levenshtein匹配目标字符串+额外文本


Using levenshtein to match target string + extra text

我正在做一个网站转换项目,我需要匹配不精确的字符串。我正在考虑使用levelshtein,但我不知道我应该为我的任务设置什么参数。

假设我有一个目标字符串elephant。我想要提取的匹配是elephant mouse,例如

<?
$target = "elephant";
$data = array(
  'elephant mouse',
  'rhinoceros',
  'alligator',
  'hippopotamus',
  'rat',
);
foreach ( $data as $datum ) {
  echo "$target >> $datum == " .  levenshtein($target, $datum) . "'n";
}

得到结果

elephant >> elephant mouse == 6
elephant >> rhinoceros == 10
elephant >> alligator == 7
elephant >> hippopotamus == 10
elephant >> rat == 7

因此,当rhinohippo在10时,在我的实际数据集中,我无法真正区分elephant mouse, ratalligator,它们在6和7时不分上下。这是伪造的数据,但在我的数据集中,长度更接近的单词只比target + extra的单词得分低得多。

如何配置levenshtein()的选项?我可以为插入、替换和删除的代价设置新的整数值。多大的权重能让我得到我想要的?

(如果你能想到更好的标题,请编辑我的帖子)。

levenshtein($target, $datum, 1, 10, 10)给我的权重

elephant >> elephant mouse == 6
elephant >> rhinoceros == 65
elephant >> alligator == 52
elephant >> hippopotamus == 64
elephant >> rat == 60

工作得很好:)插入的成本很低,而替换和删除的成本都很高。这意味着target + extra的得分很低,其中长度相等或更短,但字符不同的字符串的代价很高。

您可能应该尝试用levenshtein()匹配单个单词,而不是整个短语,因为如果短语包含与正在搜索的单词相似的内容,显然您希望将其视为一个良好的匹配。换句话说,将$datum中的每个字符串拆分为单个单词,为每个单词运行levenshtein($target, $word),并选择最小的数字。(如果$target也可以包含多个单词,您也需要拆分该单词。)

我强烈怀疑你可以通过调整插入/删除/替换成本来达到预期的效果,因为Levenshtein不考虑单个单词,只考虑整个字符串。你可以尝试使插入非常便宜,但这也会给e.g.一个很好的分数。"qwErtyLasdEdgfhdPasdxcHdfjAlkjNlkhTkjh"因为它包含了所有正确的字母