Использование Левенштейна для сопоставления целевой строки + дополнительный текст - PullRequest
Новая
       5

Использование Левенштейна для сопоставления целевой строки + дополнительный текст

1 голос
/ 10 сентября 2011

Я работаю над проектом конверсии веб-сайта, и мне нужно сопоставить неточные строки.Я смотрю на использование Левештейна, но я не знаю, какие параметры я должен установить для своей задачи.

Скажем, у меня есть целевая строка 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

Так что пока rhino и hippo равны 10,в моем фактическом наборе данных я не мог действительно отличить elephant mouse, rat и alligator, которые имеют шею и шею в 6 и 7. Это фиктивные данные, но в моем наборе данных,слова, которые ближе по длине, получают гораздо более низкий балл, чем слова, которые target + extra.

Как настроить параметры levenshtein()?Я могу установить новые целочисленные значения для стоимости вставки, замены и удаления.Какой вес даст мне то, что я хочу?

(Если вы можете придумать лучший заголовок, пожалуйста, отредактируйте мой пост).

Ответы [ 2 ]

2 голосов
/ 10 сентября 2011

Вес levenshtein($target, $datum, 1, 10, 10) дает мне 

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

, что очень хорошо работает :) Вставка стоит недорого, в то время как замена и удаление высоки.Это означает, что target + extra имеет низкую оценку, где строки одинаковой или меньшей длины, но с разными символами, имеют высокую стоимость.

1 голос
/ 10 сентября 2011

Возможно, вам следует попытаться сопоставить отдельные слова с levenshtein(), а не с целыми фразами, поскольку вы, очевидно, хотите считать фразу хорошим совпадением, если она содержит нечто, напоминающее искомое слово. Другими словами, разбейте каждую строку в $datum на отдельные слова, наберите levenshtein($target, $word) для каждого слова и выберите наименьшее число. (Если $target также может состоять из нескольких слов, вам нужно разделить и это.)

Я сильно сомневаюсь, что вы можете достичь желаемого эффекта, изменив стоимость вставки / удаления / замены, потому что Левенштейн не рассматривает отдельные слова, только строку в целом. Вы можете попытаться сделать вставку очень дешевой, но это также даст хороший результат, например, «qwErtyLasdEdgfhdPasdxcHdfjAlkjNlkhTkjh», так как содержит все правильные буквы.

...