Хороший алгоритм сравнения строк (например, Total Commander compare)

Я хочу создать скрипт сравнения строк на C ++.
Функция сравнения файлов Total Commander очень хороша:

образец общего командира


Как работает этот алгоритм?
Может ли кто-нибудь поделиться фрагментом этой функции?


c++ string algorithm compare string-comparison
person user594297    schedule 16.04.2013    source источник
comment
Вы слышали о diff или LCS?   -  person Alexey Frunze    schedule 16.04.2013
comment
возможно, попробуйте использовать что-то вроде дистанции Хэмминга. также прочтите этот пост stackoverflow.com/questions/6163611/compare-two-files   -  person Gilad    schedule 16.04.2013
comment
@Androidy Это совершенно не связано.   -  person Alexey Frunze    schedule 16.04.2013
comment
почему бы не @AlexeyFrunze? пожалуйста, объясните, что хэмминг предназначен для сравнения слов. вы также можете применить его к буферам. не идеал как LCS.   -  person Gilad    schedule 16.04.2013
comment
@Androidy Этот вопрос касается проверки идентичности двух файлов. Здесь проблема в другом, OP хочет увидеть, что и где изменилось, а не просто определить, что произошло какое-то изменение.   -  person Alexey Frunze    schedule 16.04.2013
comment
@AlexeyFrunze, хорошо, я понял. Благодарность   -  person Gilad    schedule 16.04.2013

Ответы (3)


arrow_upward
2
arrow_downward

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

Но общий алгоритм таков:

http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm

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

Также обратитесь к этому сообщению: алгоритм сравнения строк c ++

С наилучшими пожеланиями

person icbytes    schedule 16.04.2013
comment
Как вы предлагаете применить KMP к проблеме OP? - person Alexey Frunze; 16.04.2013
comment
KMP: алгоритм поиска строки = алгоритм сопоставления строки (под) строки. Отрицание этого значения приведет к созданию алгоритма несоответствия строк. Верно? - person icbytes; 16.04.2013
comment
Я не слежу за тобой. Можете ли вы привести пример того, как можно было бы использовать KMP, чтобы обнаружить, что между двумя заданными строками слово ate изменилось на eat, а затем слово on было удалено? - person Alexey Frunze; 16.04.2013
comment
Привет. Нет, я должен признать. Не сейчас. Но если Вы дадите мне немного времени, я постараюсь найти какое-то решение. - person icbytes; 17.04.2013

arrow_upward
1
arrow_downward

Для такого сравнения вы можете использовать алгоритм diff или LCS.

Ниже приведена его простая реализация на языке C:

#include <string.h>
#include <stdlib.h>
#include <stdio.h>

int lcs(const char* s1, const char* s2)
{
  size_t l1 = strlen(s1), l2 = strlen(s2);
  size_t sz = (l1 + 1) * (l2 + 1) * sizeof(size_t);
  size_t w = l2 + 1;
  size_t* dpt;
  size_t i1, i2;

  if (sz / (l1 + 1) / (l2 + 1) != sizeof(size_t) ||
      (dpt = malloc(sz)) == NULL)
  {
    printf("Not enough memory\n");
    return EXIT_FAILURE;
  }

  for (i1 = 0; i1 <= l1; i1++)
    dpt[w * i1 + 0] = 0;
  for (i2 = 0; i2 <= l2; i2++)
    dpt[w * 0 + i2] = 0;

  for (i1 = 1; i1 <= l1; i1++)
    for (i2 = 1; i2 <= l2; i2++)
    {
      if (s1[l1 - i1] == s2[l2 - i2])
      {
        dpt[w * i1 + i2] = dpt[w * (i1 - 1) + (i2 - 1)] + 1;
      }
      else if (dpt[w * (i1 - 1) + i2] > dpt[w * i1 + (i2 - 1)])
      {
        dpt[w * i1 + i2] = dpt[w * (i1 - 1) + i2];
      }
      else
      {
        dpt[w * i1 + i2] = dpt[w * i1 + (i2 - 1)];
      }
    }

  i1 = l1; i2 = l2;
  for (;;)
  {
    if ((i1 > 0) && (i2 > 0) && (s1[l1 - i1] == s2[l2 - i2]))
    {
      printf("%c", s1[l1 - i1]);
      i1--; i2--; continue;
    }
    else
    {
      if (i1 > 0 &&
          (i2 == 0 || dpt[w * (i1 - 1) + i2] >= dpt[w * i1 + (i2 - 1)]))
      {
        printf("-%c", s1[l1 - i1]);
        i1--; continue;
      }
      else if (i2 > 0 &&
               (i1 == 0 || dpt[w * (i1 - 1) + i2] < dpt[w * i1 + (i2 - 1)]))
      {
        printf("+%c", s2[l2 - i2]);
        i2--; continue;
      }
    }

    break;
  }
  printf("\n");

  free(dpt);
  return EXIT_SUCCESS;
}

int main(int argc, char** argv)
{
  const char *s1, *s2;
  if (argc == 3)
  {
    s1 = argv[1]; s2 = argv[2];
  }
  else
  {
    printf("Usage:\n  lcs-diff.exe <string1> <string2>\n\n");
    s1 = "I ate apple on yesterday"; s2 = "I eat apple yesterday";
    printf("Sample comparison:\n\n  \"%s\" vs \"%s\":\n\n", s1, s2);
  }

  return lcs(s1, s2);
}

Вывод (ideone):

Usage:
  lcs-diff.exe <string1> <string2>

Sample comparison:

  "I ate apple on yesterday" vs "I eat apple yesterday":

I +eat-e apple -o-n- yesterday
person Alexey Frunze    schedule 18.04.2013

arrow_upward
0
arrow_downward

С нуля я бы подошел к этой проблеме так (псевдокод):

String[] sarr1 = string1.split();

for (int i1 =0; i1<sarr1.length; i1++) {
  if (!string2.contains(sarr[i1]) {
    markWordRed(string1, sarr[i1]);
  }
}

String[] sarr2 = string2.split();
for (int i2 =0; i2<sarr2.length; i2++) {
  if (!string1.contains(sarr[i2]) {
    markWordRed(string2, sarr[i2]);
  }
}

Начиная с этого, дополнительно можно:

  • проверьте порядок слов, а не только то, существуют они или нет

  • проверить сходство каждого ненайденного слова со всеми ненайденными словами во второй строке и показать буквенные различия

person Dariusz    schedule 16.04.2013