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

Ответ 1

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

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

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

Кажется, что он тестирует "сколько раз какой-либо отдельный char на param1 находится в param2", и, следовательно, результат будет другим, если вы поменяете параметры. Сообщается как bug, который никем не подтвержден.

Теперь вышесказанное одно и то же для реализаций 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 и исправления. Престижность там.

Ответ 2

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

Позвольте мне начать, объясняя, как работает Similar_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 находятся на противоположных концах двух строк, неясно, что NLP энтузиасты или другие литературные эксперты должны сказать об этой конкретной ситуации.

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

Различные результаты, которые вы испытывали на основе порядка ввода, были связаны с тем, как ведет себя 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

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

Похожие тексты: JavaScript Edition

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

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

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

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

Demystified!

Ответ 3

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

Ответ 4

Описание 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.