Где можно найти алгоритмы, которые более точно определяют орфографию неуместных символов, чем методы 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! / Йонас
Вот решение, к которому я придумал. Это основано на предложении Тима сравнить порядок последующих чахатчиков. Некоторые результаты:
Я уверен, что я не совершенен, и что он может быть оптимизирован, но, тем не менее, он, похоже, дает результаты, которые я получаю … Одно слабое место в том, что, когда строки имеют разную длину, это приводит к другому результату, когда значения меняются местами …
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 ОК!
ivanov ivan 2 / ivanov ivan: 1 o_O
ivanov i van / ivanov i: 1.1363636363636 OMG!
В дополнение к levenshtein () и аналогичному_text (), есть также:
soundex () : возвращает четырехсимвольную звуковую клавишу слова, которая должна быть такой же, как и клавиша для любого аналогичного звучания.
metaphone () : похоже на soundex и, возможно, более эффективен для вас. Это более точно, чем soundex (), поскольку он знает основные правила английского произношения. Генерируемые метафоном ключи имеют переменную длину.
@Tim: Я действительно ищу способ обработки / измерения сходства в контексте педагогической игры. Предположим, что задача ученика – выбрать объекты из пула и поместить эти объекты в определенном порядке (сортировать их по алфавиту или тому подобное). Затем мне нужен способ измерения сходства между ответом студентов и правильным
Алгоритмы для вычисления степени правильности порядка символов в слове (т. Е. Его правописания) могут сильно отличаться от алгоритма для измерения правильного порядка слов в списке. То, как алгоритмы орфографии обрабатывают пропуски или диктографию или транспозиции, может не очень хорошо применяться в вашем случае использования.
Если вы заранее знаете порядок элементов и знаете количество элементов, тогда вы можете просто пропустить ответ и сравнить значение-в-позиции с поправкой-значением-в-позиции и получить процентное значение. Тем не менее, это было бы грубой мерой и вводить в заблуждение, поскольку если бы цель вашей игры заключалась в том, чтобы проверить, скажет ли геймер, что такое алфавитная сортировка, а геймеру было неправильно записано первое слово, каждое слово может оказаться в неправильном положении даже если слова были в другом правильном алфавитном порядке:
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");