Где можно найти алгоритмы, которые более точно определяют орфографию неулокальных символов, чем методы levenshtein() и php Similar_text()?
Пример:
similar_text('jonas', 'xxjon', $similar); echo $similar; // returns 60
similar_text('jonas', 'asjon', $similar); echo $similar; // returns 60 <- although more similar!
echo levenshtein('jonas', 'xxjon'); // returns 4
echo levenshtein('jonas', 'asjon'); // returns 4 <- although more similar!
/Jonas
Вот решение, к которому я придумал. Это основано на предположении Тима о сравнении порядка последующих символов. Некоторые результаты:
Я уверен, что я не совершенен, и что он может быть оптимизирован, но, тем не менее, он, похоже, дает результаты, которые я после... Одним из слабых мест является то, что когда строки имеют разную длину, он производит разные результаты, когда значения меняются местами...
static public function string_compare($str_a, $str_b)
{
$length = strlen($str_a);
$length_b = strlen($str_b);
$i = 0;
$segmentcount = 0;
$segmentsinfo = array();
$segment = '';
while ($i < $length)
{
$char = substr($str_a, $i, 1);
if (strpos($str_b, $char) !== FALSE)
{
$segment = $segment.$char;
if (strpos($str_b, $segment) !== FALSE)
{
$segmentpos_a = $i - strlen($segment) + 1;
$segmentpos_b = strpos($str_b, $segment);
$positiondiff = abs($segmentpos_a - $segmentpos_b);
$posfactor = ($length - $positiondiff) / $length_b; // <-- ?
$lengthfactor = strlen($segment)/$length;
$segmentsinfo[$segmentcount] = array( 'segment' => $segment, 'score' => ($posfactor * $lengthfactor));
}
else
{
$segment = '';
$i--;
$segmentcount++;
}
}
else
{
$segment = '';
$segmentcount++;
}
$i++;
}
// PHP 5.3 lambda in array_map
$totalscore = array_sum(array_map(function($v) { return $v['score']; }, $segmentsinfo));
return $totalscore;
}
Пожалуйста, будьте осторожны с использованием string_compare:
ivanov ivan/ivanov ivan: 1 OK!
ivanov ivan 2/ivanov ivan: 1 o_O
ivanov я van/ivanov i: 1.1363636363636 OMG!
В дополнение к levenshtein() и аналогичному_text(), также:
soundex(): возвращает четырехзначную звуковую клавишу слова, которая должна быть такой же, как ключ для любого похожего слова.
metaphone(): похоже на soundex и, возможно, более эффективен для вас. Это более точно, чем soundex(), поскольку он знает основные правила английского произношения. Генерируемые метафоном ключи имеют переменную длину.
@Tim: Я действительно ищу способ обрабатывать/измерять сходства в педагогический игровой контекст. Пусть говорят что задача ученика - выбрать объекты из пула, и объекты в определенном порядке (сортировать их по алфавиту или тому подобное). Мне тогда нужно способ измерения сходства между ответами студентов и правильный
Алгоритмы для вычисления степени правильности порядка символов в слове (например, его правописания) могут сильно отличаться от алгоритма для измерения правильного порядка слов в списке. Как алгоритмы орфографии обрабатывают пропуски или dittography или транспозиции, могут не очень хорошо применяться в вашем случае использования.
Если вы заранее знаете порядок элементов и знаете количество элементов, то вы можете просто пропустить ответ и сравнить значение-в-позиции с поправкой-значением-в-позиции и получить процентное значение, верный. Тем не менее, это было бы грубой мерой и вводить в заблуждение, поскольку если бы цель вашей игры заключалась в том, чтобы проверить, скажет ли геймер, что такое алфавитная сортировка, а геймеру было неправильно записано первое слово, каждое слово может оказаться в неправильном положении даже если слова были в другом правильном алфавитном порядке:
banana
blackberry
blueberry
cherry
fig
grapefruit
orange
pear
persimmon
raspberry
apple
Итак, что вы могли бы сделать, чтобы повысить точность ваших измерений в нашей гипотетической ситуации, так это: прокрутите список ответов геймера, чтобы посмотреть, сразу ли за ним отвечает правильное слово; каждый раз, когда за словом следует правильное слово, вы должны дать игроку точку. Игрок, который подготовил список выше, получит 9 баллов из возможных 10, и этот счет действительно точно отражает понимание игроками правил сортировки по алфавиту.
Я обнаружил, что Jaro Winkler также хорош для орфографических ошибок и небольших различий между строками. Я модифицировал этот код для объектно-ориентированного:
class StringCompareJaroWinkler
{
public function compare($str1, $str2)
{
return $this->JaroWinkler($str1, $str2, $PREFIXSCALE = 0.1 );
}
private function getCommonCharacters( $string1, $string2, $allowedDistance ){
$str1_len = mb_strlen($string1);
$str2_len = mb_strlen($string2);
$temp_string2 = $string2;
$commonCharacters='';
for( $i=0; $i < $str1_len; $i++){
$noMatch = True;
// compare if char does match inside given allowedDistance
// and if it does add it to commonCharacters
for( $j= max( 0, $i-$allowedDistance ); $noMatch && $j < min( $i + $allowedDistance + 1, $str2_len ); $j++){
if( $temp_string2[$j] == $string1[$i] ){
$noMatch = False;
$commonCharacters .= $string1[$i];
$temp_string2[$j] = '';
}
}
}
return $commonCharacters;
}
private function Jaro( $string1, $string2 ){
$str1_len = mb_strlen( $string1 );
$str2_len = mb_strlen( $string2 );
// theoretical distance
$distance = (int) floor(min( $str1_len, $str2_len ) / 2.0);
// get common characters
$commons1 = $this->getCommonCharacters( $string1, $string2, $distance );
$commons2 = $this->getCommonCharacters( $string2, $string1, $distance );
if( ($commons1_len = mb_strlen( $commons1 )) == 0) return 0;
if( ($commons2_len = mb_strlen( $commons2 )) == 0) return 0;
// calculate transpositions
$transpositions = 0;
$upperBound = min( $commons1_len, $commons2_len );
for( $i = 0; $i < $upperBound; $i++){
if( $commons1[$i] != $commons2[$i] ) $transpositions++;
}
$transpositions /= 2.0;
// return the Jaro distance
return ($commons1_len/($str1_len) + $commons2_len/($str2_len) + ($commons1_len - $transpositions)/($commons1_len)) / 3.0;
}
private function getPrefixLength( $string1, $string2, $MINPREFIXLENGTH = 4 ){
$n = min( array( $MINPREFIXLENGTH, mb_strlen($string1), mb_strlen($string2) ) );
for($i = 0; $i < $n; $i++){
if( $string1[$i] != $string2[$i] ){
// return index of first occurrence of different characters
return $i;
}
}
// first n characters are the same
return $n;
}
private function JaroWinkler($string1, $string2, $PREFIXSCALE = 0.1 ){
$JaroDistance = $this->Jaro( $string1, $string2 );
$prefixLength = $this->getPrefixLength( $string1, $string2 );
return $JaroDistance + $prefixLength * $PREFIXSCALE * (1.0 - $JaroDistance);
}
}
$jw = new StringCompareJaroWinkler();
echo $jw->compare("jonas","asjon");