Как сравнить набор строк, чтобы найти общие подстроки - PullRequest
Новая
       76

Как сравнить набор строк, чтобы найти общие подстроки

1 голос
/ 13 января 2011

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

Например:

  1. Здравствуйте, я строка первая.Я люблю яблоки и апельсины.Мы все здесь.
  2. Здравствуйте, я вторая строка.Я люблю яблоки и апельсины.Мы все здесь.
  3. Здравствуйте, я строка третья.Я люблю яблоки и апельсины.Мы все здесь.
  4. Здравствуйте, я четвертая строка.Я люблю яблоки и апельсины.Мне нравится выражать свою индивидуальность.

Мне бы хотелось, чтобы скрипт сообщал мне, каковы общие элементы между строками выше определенного порога (например, 5 символов).

В идеале я бысказал

  • "Я люблю яблоки и апельсины" встречается во всех файлах
  • "Здравствуйте, я строка" встречается во всех файлах
  • "Мы все строки здесь"встречается в трех файлах.

Если существуют функции для этого в технологиях, с которыми я знаком - SQL, Javascript, PHP, Ruby или Bash - я буду очень счастлив ...

Большое спасибо,

Джек

1 Ответ

2 голосов
/ 13 января 2011

Это сложная проблема, известная как Самая длинная общая подпоследовательность .

Вот реализация Python алгоритма с использованием динамического программирования: http://www.algorithmist.com/index.php/Longest_Common_Subsequence

Я не думаю, что любая стандартная библиотека (C, Java, PHP, Python, Javascript, Ruby и т. Д.) Поставляется с такой функцией. Но вы можете найти здесь реализации: http://www.google.com/codesearch?q=%22longest+common+subsequence%22

...