Как работает подобный_текст?

Казалось бы, функция использует различную логику в зависимости от порядка параметров. Я думаю, что в игре есть две вещи.

Сначала рассмотрим этот пример:

 echo similar_text('test','wert'); // 1 echo similar_text('wert','test'); // 2 

Похоже, что он тестирует «сколько раз какой-либо отдельный символ на param1 находится в param2», и, следовательно, результат будет другим, если вы поменяете параметры. Сообщается, что это ошибка , которая никому не подтверждена.

Теперь вышеприведенное одно и то же для PHP и javascript-реализаций – порядок paremeter оказывает влияние, поэтому, говоря, что JS-код не будет делать это, это неправильно. Я думаю, что можно утверждать, что в качестве предполагаемого поведения. Не уверен, что это так.

Во-вторых – что не кажется правильным, это пример слов MYSQL / PHP. При этом версия javascript дает 3 не относящихся к порядку параметров, тогда как PHP дает 2 и 3 (и из-за этого процент одинаково отличается). Теперь фразы «PHP IS GREAT» и «WITH MYSQL» должны содержать 5 символов, не имеющих отношения к тому, что вы сравниваете: H, I, S и T, по одному, плюс один для пустого пространства. Для того, чтобы они имели 3 символа, «H», «» и «S», поэтому, если вы посмотрите на упорядочение, правильный ответ должен быть 3 в обоих направлениях. Я изменил код C на исполняемую версию и добавил некоторый вывод, поэтому можно увидеть, что там происходит ( ссылка на кодовое слово ):

 #include<stdio.h> /* {{{ php_similar_str */ static void php_similar_str(const char *txt1, int len1, const char *txt2, int len2, int *pos1, int *pos2, int *max) { char *p, *q; char *end1 = (char *) txt1 + len1; char *end2 = (char *) txt2 + len2; int l; *max = 0; for (p = (char *) txt1; p < end1; p++) { for (q = (char *) txt2; q < end2; q++) { for (l = 0; (p + l < end1) && (q + l < end2) && (p[l] == q[l]); l++); if (l > *max) { *max = l; *pos1 = p - txt1; *pos2 = q - txt2; } } } } /* }}} */ /* {{{ php_similar_char */ static int php_similar_char(const char *txt1, int len1, const char *txt2, int len2) { int sum; int pos1, pos2, max; php_similar_str(txt1, len1, txt2, len2, &pos1, &pos2, &max); if ((sum = max)) { if (pos1 && pos2) { printf("txt here %s,%s\n", txt1, txt2); sum += php_similar_char(txt1, pos1, txt2, pos2); } if ((pos1 + max < len1) && (pos2 + max < len2)) { printf("txt here %s,%s\n", txt1+ pos1 + max, txt2+ pos2 + max); sum += php_similar_char(txt1 + pos1 + max, len1 - pos1 - max, txt2 + pos2 + max, len2 - pos2 - max); } } return sum; } /* }}} */ int main(void) { printf("Found %d similar chars\n", php_similar_char("PHP IS GREAT", 12, "WITH MYSQL", 10)); printf("Found %d similar chars\n", php_similar_char("WITH MYSQL", 10,"PHP IS GREAT", 12)); return 0; } 

результат выводится:

 txt here PHP IS GREAT,WITH MYSQL txt here P IS GREAT, MYSQL txt here IS GREAT,MYSQL txt here IS GREAT,MYSQL txt here GREAT,QL Found 3 similar chars txt here WITH MYSQL,PHP IS GREAT txt here TH MYSQL,S GREAT Found 2 similar chars 

Таким образом, можно видеть, что при первом сравнении функция обнаружила «H», «» и «S», но не «T», и получила результат 3. Второе сравнение найдено «I» и «T», но не 'H', '' или 'S' и, таким образом, получил результат 2.

Причину этих результатов можно увидеть из результата: алгоритм берет первую букву в первой строке, содержащую вторую строку, подсчитывает и отбрасывает символы до этого со второй строки . Вот почему он пропускает символы между ними, и именно это вызывает разницу, когда вы меняете порядок символов.

То, что происходит, может быть преднамеренным, а может и нет. Однако это не так, как работает JavaScript. Если вы распечатаете то же самое в версии javascript, вы получите следующее:

 txt here: PHP, WIT txt here: P IS GREAT, MYSQL txt here: IS GREAT, MYSQL txt here: IS, MY txt here: GREAT, QL Found 3 similar chars txt here: WITH, PHP txt here: W, P txt here: TH MYSQL, S GREAT Found 3 similar chars 

показывая, что версия javascript делает это по-другому. Что делает версия javascript, так это то, что он находит «H», «» и «S» в том же порядке в первом сравнении, и те же «H», «» и «S» также на втором – так что в этом случае порядок параметров не имеет значения.

Я бы сказал, что версия javascript – это более правильный способ сделать это, но это предположение. В любом случае, поскольку javascript предназначен для дублирования кода функции PHP, он должен вести себя одинаково – вот почему я отправил отчет об ошибке на основе анализа @Khez и исправления. Кудос там.

Это был действительно интересный вопрос, спасибо за то, что вы дали мне загадку, которая оказалась очень полезной.

Позвольте мне начать, объясняя, как работает lik_text .

Похожие тексты: Алгоритм

Это алгоритм деления и покорения на основе рекурсии. Он работает, сначала обнаруживая самую длинную общую строку между двумя входами и разбивая проблему на подмножества вокруг этой строки.

Примеры, которые вы использовали в своем вопросе, фактически выполняют только одну итерацию алгоритма . Единственные, кто не использует одну итерацию, а те, которые дают разные результаты, – это комментарии php.net .

Вот простой пример, чтобы понять основную проблему, стоящую за simple_text, и, надеюсь, дать некоторое представление о том, как это работает.

Похожие тексты: The Flaw

 eeeefaaaaafddddd ddddgaaaaagbeeee Iteration 1: Max = 5 String = aaaaa Left : eeeef and ddddg Right: fddddd and geeeee 

Надеюсь, что изъяна уже очевидна. Он будет проверяться непосредственно слева и справа от самой длинной согласованной строки в обеих входных строках. Этот пример

 $s1='eeeefaaaaafddddd'; $s2='ddddgaaaaagbeeee'; echo similar_text($s1, $s2).'|'.similar_text($s2, $s1); // outputs 5|5, this is due to Iteration 2 of the algorithm // it will fail to find a matching string in both left and right subsets 

Честно говоря, я не уверен, как следует рассматривать этот случай. Можно видеть, что в строке всего 2 символа. Но как eeee, так и dddd находятся на противоположных концах двух строк, неясно, что энтузиасты НЛП или другие литературные эксперты должны сказать об этой конкретной ситуации.

Похожие тексты: непоследовательные результаты по обмену аргументами

Различные результаты, которые вы испытывали на основе порядка ввода, были связаны с тем, как ведет себя alogirthm (как упоминалось выше). Я дам окончательное объяснение тому, что происходит.

 echo similar_text('test','wert'); // 1 echo similar_text('wert','test'); // 2 

В первом случае есть только одна итерация:

 test wert Iteration 1: Max = 1 String = t Left : and wer Right: est and 

У нас есть только одна итерация, потому что пустые / нулевые строки возвращают 0 при рекурсии. Таким образом, этот алгоритм заканчивается, и мы получаем результат: 1

Однако во втором случае мы сталкиваемся с несколькими итерациями:

 wert test Iteration 1: Max = 1 String = e Left : w and t Right: rt and st 

У нас уже есть общая строка длины 1. Алгоритм в левом подмножестве заканчивается на 0 совпадений, но справа:

 rt st Iteration 1: Max = 1 String = t Left : r and s Right: and 

Это приведет к нашему новому и окончательному результату: 2

Я благодарю вас за этот очень информативный вопрос и возможность снова напасть на C ++.

Похожие статьи:

Короткий ответ: код javascript не реализует правильный алгоритм

 sum += this.similar_text(first.substr(0, pos2), second.substr(0, pos2)); 

Очевидно, это должно быть first.substr(0,pos1)

Примечание. Код JavaScript был исправлен с помощью eis в предыдущем коммите . Спасибо @eis

Demystified!

 first String = aaaaaaaaaa = 10 letters second String = aaaaa = 5 letters first five letters are similar a+a a+a a+a a+a a+a a a a a a ( <similar_letters> * 200 ) / (<letter_count_first_string> + <letter_count_second_string>) ( 5 * 200 ) / (10 + 5); = 66.6666666667 

Описание int similar_text (строка $ first, строка $ second [, float & $ percent])

Это вычисляет сходство между двумя строками, как описано в Oliver [1993]. Обратите внимание, что эта реализация не использует стек, как в псевдокоде Оливера, а рекурсивные вызовы, которые могут ускорить процесс или не ускорить его. Заметим также, что сложность этого алгоритма O (N ** 3), где N – длина самой длинной строки. параметры

первый

 The first string. 

второй

 The second string. 

процент

 By passing a reference as third argument, similar_text() will calculate the similarity in percent for you.