Как найти уникальные последовательности символов в двух строках?

Question

[Mirgorod]

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


Например:
www.youtube.com/user/grickle#p/u/0/tuhZuMl9StM
www.youtube.com/user/grickle#p/u/3/hnvkIQHv0OQ
www.youtube.com/user/grickle#p/u/7/cjT2Huux34g
www.youtube.com/user/grickle#p/u/2/Osex3fXi_OA


Заранее спасибо за помощь!

Comments

[Сергей Наломенко]

Это относится только к последовательностям, находящимся в конце строки?

[Mirgorod]

нет

[Mirgorod]

Все строки почти одинаковые, но имеют что-то уникальное.

[Сергей Наломенко]

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

[Mirgorod]

нет

Answer 1

[m08pvv]

Может проще найти максимальную совпадающую подстроку?

Comments

[m08pvv]

Вот, например, ну а что не является общим — отличается

[bobry]

Какая то у вас странная логика, тут же на выходе только максимальная общая подстрока — никаких слов о единственности нет, т.е. вполне могут найтись другие общие строки меньшей длины.

[m08pvv]

Не вопрос — алгоритм, описанный на Википедии, позволяет найти все общие подстроки.
Сортируем их по размеру и всё ОК — можем выбрать все «большие» общие подстроки.
Тут же ещё всё зависит от задачи — может быть можно даже проще сделать.

Answer 2

[yopopt]

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

1. /**
2. * strings - массив исходных строк
3. * result - массив уникальные последовательности символов
4. */
5. var strings = [
6.   'www.youtube.com/user/grickle#p/u/dasdas/0/tuhZuMl9StM',
7.   'www.youtube.com/user/grickle#p/u/dasd as/3/hnvkIQHv0OQ',
8.   'www.youtube.com/user/grickle#p/u/vcx bxcv/7/cjT2Huux34g',
9.   'www.youtube.com/user/grickle#p/u/54354/2/Osex3fXi_OA'
10.   ],
11.   temp = [],
12.   result = [],
13.   repeat = {},
14.   newStrings = {};
15.   
16.   /**
17.    * Обходим исходный массив и разбиваем его по повторяющимся символам,
18.    * здесь это слеши. Создаём объект с ключами из уникальных строк, а
19.    * значения - индексы этих строк в разделённой оригинальной строке.
20.    * одинаковые же части сохраняем в массив повторяющихся.
21.    */
22.   for(var i = 0; i<strings.length; i++) {
23.     temp[i] = strings[i].split('/');
24.     result[i] = '';
25.     for(var j = 0; j<temp[i].length; j++) {
26.       if(temp[i][j] in newStrings) {
27.         repeat[temp[i][j]] = 1;
28.       }
29.       newStrings[temp[i][j]] = i;
30.     }
31.   }
32.   
33.   /**
34.    * Склеиваем уникальные части строки в одну.
35.    */
36.   for(var key in newStrings) {
37.     if(!(key in repeat))
38.      result[newStrings[key]]+=(result[newStrings[key]]!=''?'/':'')+key;
39.   }

Answer 3

[Сергей Береснев]

Кстати, в приведённых примерах будут две строки. Например, для первой «0» и «tuhZuMl9StM».

А вот моё неоптимальное решение «в лоб».

$strs[] = 'www.youtube.com/user/grickle#p/u/0/tuhZuMl9StM';
$strs[] = 'www.youtube.com/user/grickle#p/u/3/hnvkIQHv0OQ';
$strs[] = 'www.youtube.com/user/grickle#p/u/7/cjT2Huux34g';
$strs[] = 'www.youtube.com/user/grickle#p/u/2/Osex3fXi_OA';
$return = array();

foreach ($strs as $key => $str1)
    {
    $return[$key] = array();
    foreach($strs as $str2)
        {
        $astr1 = str_split($str1);
        $astr2 = str_split($str2);
        $array_diff = array_diff_assoc($astr1, $astr2);
        $return[$key] = $return[$key] + $array_diff;
        }
    ksort($return);
    }
var_dump($return);

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

Answer 4

[Марсель Мархабулин]

Если массив ссылок хранится в файле, то товарищи выше уже дали варианты.
Могу предположить, что сборка ссылок хранится в БД. Тогда, в случае MySQL выборка уникальный значений в столбце | (столбце + строке) будет находиться стандартным запросом SELECT DISTINCT `column` FROM `database.table` LIMIT `max_rows`;

Answer 5

[Константин]

sort(row);
row = "";
while (row_next)
{
if( row == row_next) // your condition
{
print('blbeleblbele');
...
}
row = row_next;
}


Comments

[Константин]

sort(row_next);

[Константин]

Я наверное поспешил, но принцип такой:
отсортировать и потом пройти массив и сравнивать каждые рятом 2 строки, стравнивать можно например левенштайном (http://en.wikipedia.org/wiki/Levenshtein_distance)

Answer 6

[Сергей Наломенко]

Можно попробовать библиотеки, используемые в diff'e, который сравнивает разные версии файлов на предмет отличий.

Comments

[Mirgorod]

можете подробнее?

[Сергей Наломенко]

собственно, алгоритм описан тут:
ru.wikipedia.org/wiki/Diff

[Mirgorod]

Хмм, почитал, но нужно в каждой строке получить уникальные последовательности, а не одну строку, которая уникальная для двух исходных.

[Сергей Наломенко]

А что мешает модифицировать алгоритм под свою задачу? Просто считаем, что каждый символ — отдельная строка в файле. Сравниваем, а потом «склеиваем» уникальные псевдо-строки и получаем уникальный сегмент.

[Сергей Наломенко]

А еще, по сути, их потом можно местами поменять, и получить две уникальные строки:
1) Сравниваем, как A отличается от B (в итоге имеем некое uA, уникальное для строки A)
2) Сравниваем, как отличается B от A ((в итоге имеем некое uB, уникальное для строки B)
3) На выходе имеем uA и uB

[Mirgorod]

lab.mirgorod.us/diff/ — вот пример сравнения, можете глянуть? Там почему-то проблема с нульом.

Answer 7

[NikoB]

www.php.su/functions/?levenshtein

Comments

[Mirgorod]

смотрел эту функцию, но так и не понял как найти индексы уникальных последовательностей в строке.

[NikoB]

Расстояние Левенштейна — это минимальное количество вставок, замен и удалений символов, необходимое для преобразования str1 в str2
В общем делаете так: сравнивайте строки, допустим две строки, и поставить порог уникальности, т.е. если расстояние левенштейна больше 3 то строки уникальные.

[NikoB]

а вообще что значит уникальные? чтобы хотя бы один символ отличался?

[Mirgorod]

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

Answer 8

[Анатолий]

Есть вариант в лоб, для ленивых:
есть два цикла, первый проходит по первой строке, второй по второй
на каждую итерацию первого цикла нужно проверять вторую строку с начала
при совпадении символов, второй цикл начинается с позиции равной количеству совпаденных символов
наиболее длинное совпадение сохраняем и заменяем ранее сохраненное, если оно есть
!!!
PROFIT

если кто не понял
abcd
cd
a=c — no
b=c — no
c=c — yes
d=d — yes
max = cd

Это тупейший поиск похожих вхождений, как найти разницу думаю не составит труда =)

Comments

[Анатолий]

«при совпадении символов, второй цикл начинается с позиции равной количеству совпаденных символов»
Извеняюсь, с позиции совпадения + количество совпаденных символов