Подтвердить что ты не робот

Регулярное выражение для частичной длины совпадения - сходство строк

Скажем, у меня есть строка "Torcellite" и еще одна строка "Tor" - длина подобия этих двух строк равна 3, так как оба они начинаются с "Tor". Теперь другая строка "christmas" и "mas" будет иметь сходство 0, так как они не начинаются с одного и того же набора символов.

В обоих случаях вторая строка является суффиксом первой строки.

Более ясный пример:

Длина строки: от 1 до 10 ^ 5

Строка: abaabc

Суффиксы: abaabc, baabc, aabc, abc, bc, c

Сходство: abaabc, none, a, ab, none, none

Сходство Длина: 6, 0, 1, 2, 0, 0

Ответ: 6 + 0 + 1 + 2 + 0 + 0 = 9

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

Алгоритм:

  • Найти все подстроки данной строки.

  • Сделайте шаблон из подстрок суффиксов.

    for(int i=1; i<substrings[i].length; i++) {
    Pattern p = Pattern.compile("^"+substrings[i].substring(0, i));
    Matcher m = p.find(string); //the given string for which similarities need to be  calculated
    if(m.find())
        similaryLengths +=  i;
}

  • Сложность для этого становится примерно O (n ^ 2), так как мне нужно пробежать строку для суффиксов, а затем подстроки для шаблонов.

  • Я думал об использовании группировки в шаблоне, чтобы найти группы, но я не уверен, как будет выглядеть регулярное выражение. То, что я имею в виду, для самой первой подстроки: ((((((a)b)a)a)b)c), а затем найти самое длинное групповое совпадение.

Есть ли более эффективный алгоритм, который может его достичь?

4b9b3361

ОТВЕТЫ

Ответ 1

Наилучшим подходом, безусловно, было бы создание дерева суффиксов на входной строке. Деревья суффиксов деревьев принимают только O (n) время, где n - длина строки. Дерево суффикса логически состоит из дерева, в котором все суффиксы строки могут быть найдены путем перехода от корня к каждому листу. Вы можете прочитать Википедию для получения более подробной информации о том, как эти деревья работают.

По сути, дерево суффиксов позволит вам просто переделать текущую проблему как "поиск" исходной строки в дереве суффиксов. Когда вы идете по дереву, вы подсчитываете количество суффиксов в каждом поддереве и умножаетесь на свою текущую длину совпадения, чтобы определить свой балл. Этот "поиск" также занимает время O (n).

Итак, конечный результат заключается в том, что вы можете решить проблему в гарантированном O (n) времени и O (n) пространстве, с O (n) временем предварительной обработки. Это довольно эффективно! И нет "худших случаев", которые производят квадратичное поведение. С этим вы, вероятно, можете легко обрабатывать строки до 10 ^ 7 в длину.

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

Ответ 2

Алгоритм Simliar, уже опубликованный Валдаром Моридиным, но без необходимости создавать подстроки (каждый вызов substring создаст новый объект String, который содержит копию указанного диапазона char[] своего источника). Это не улучшит временную сложность, но, вероятно, уменьшит общее время выполнения для постоянного фактора:

public static int partialSuffixMatch(CharSequence input) {
    int count = input.length();
    for (int i = 1; i < input.length(); i++) {
        for (int a = 0, b = i; b < input.length(); a++, b++) {
            if (input.charAt(a) != input.charAt(b))
                break;
            count++;
        }
    }
    return count;
}

После короткого разминки этот алгоритм обрабатывает String с 10000 равными знаками примерно за 40 мс на моем компьютере и со 100 000 равными знаками примерно за 4 секунды.

Ответ 3

Вот как я буду делать то, что вы описали выше. Я не знаю, чего это должно выполнить, но поскольку вы указали, что нужно только совместить начало строк, даже если это O (n ^ 2), большую часть времени он не будет работать нигде около полной длины n. Худший случай - это, очевидно, строка типа "aaaaaaaaaaaaaaaaa". Это занимает менее 5 секунд для обработки строки из 60 000 символов 'a' на моей машине.

Я не вижу необходимости использовать накладные расходы для генерации и компиляции регулярных выражений для строгого соответствия префикса. Я пропустил этот момент?

int similarity(String input) {
    int count = 0;
    for (int i = 0; i < input.length() ; i++) {
        String sub = input.substring(i);
        for (int j = 0; j < sub.length(); j++) {
            if (input.charAt(j) != sub.charAt(j))
                break;
            count++;
        }
    }
    return count;
}

Ответ 4

Из примера abaabc, я понимаю, вы пытаетесь найти все подстроки, соответствующие началу исходной строки. Это можно сделать с помощью одного регулярного выражения, немного похожего на шаблон, который вы предложили. Конечно, это регулярное выражение будет пропорционально по длине исходной строке. Само регулярное выражение очень простое; он представляет всю строку, но хвост строки (произвольной длины) является необязательным. Эффективно это регулярное выражение соответствует любому префиксу строки. Для строки abcdef регулярное выражение:

(?=(a(?:b(?:c(?:d(?:ef?)?)?)?)?))

Примечания:

  • Я использовал (?: ... ) для каждого подшаблона, кроме внешнего, чтобы избежать множества ненужных захватов.
  • Я использовал шаблон поиска (?= ... ), потому что совпадения могут (и будут) перекрываться. Без него самое первое совпадение (будучи всей строкой abcdef) будет потреблять весь ввод, в результате чего будут пропущены все другие возможные совпадения.

Конечно, abcdef не является интересным примером; он не имеет повторяющихся подстрок, поэтому регулярное выражение имеет только одно совпадение, которое представляет собой всю строку, abcdef. Ваш пример abaabc приятнее, поэтому я сделал для него скрипку. Как указано вами, он находит 3 совпадения: abaabc, a, ab.
http://regex101.com/r/vJ8uQ9/1

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

function generateRegex(string input)
{
    return input.substring(0, 1) +
           (input.length > 2 ? "(?:" + generateRegex(input.substring(1)) + ")" : input.substring(1)) +
           "?";
}

string myRegex = "(?=(" + generateRegex(myInput) + "))";

У меня не было тестовой среды Java, но я тестировал ее на JavaScript.
Fiddle: http://jsfiddle.net/gqehcjf9/1/

Производительность кажется ОК (менее секунды для строки из 9000 символов), но при тестировании на строку из более чем 9361 символов (Firefox 31.0) я получил исключение "регулярное выражение слишком сложное". Я надеюсь, что Java regex engine менее ограничительный. Если нет, то есть одна возможная оптимизация. Если вы уверены, что повторяющиеся подстроки никогда не будут длиннее, например, 1000 символов, тогда вы можете подумать о создании регулярного выражения только для первых 1000 символов строки. Вам будет недоставать часть первого совпадения (т.е. Целая строка), но исправление, которое не вызывает затруднений.

Ответ 5

Как это выполняется в вашем наборе данных?

int sum = s.length;
for (int i = 1; i < s.length; i++) {
    for (int j = i; j < s.length; j++) {
        for (int k = 0; k < s.length - j; k++) {
            if (s.charAt(i+k) != s.charAt(j+k)) break;
            sum++;
        }
    }
}

Вместо итерации я вы можете найти следующее вхождение s.charAt(0).

Ответ 6

Пожалуйста, попробуйте следующие методы. Я протестировал это. Любая входная строка (длина от 1 ~ 10 ^ 5), время выполнения на моем ПК меньше времени 20 мс.

public static int oneTry(CharSequence input) {
    int tail = input.length();
    for (int i = 1; i < input.length(); i++) {
        if (input.charAt(i) == input.charAt(0)) {
            tail = i;
            break;
        }
    }

    int count = 0;

    int head = 0;
    int next = 0;
    int base = 0;
    int two = -1;
    boolean start = false;
    boolean end = false;
    for (int i = tail; i < input.length(); i++) {
        if (input.charAt(i) == input.charAt(next)) {

            count++;

            if (next>0 && !start && input.charAt(i) == input.charAt(0)) {
                base = 1;
                start = true;
            }

            if (start) {
                if (!end && input.charAt(i) == input.charAt(head)) {
                    count = count + base;
                    head++;
                    head = head < tail ? head : 0;
                    if(head == 0) {
                        base++;
                    }
                } else {
                    end = true;
                }

                if(end) {
                    if(two <0 && input.charAt(i) == input.charAt(0)) {
                        two = i;
                    }
                }
            }

            next++;

            if(i==input.length()-1 && two > 0) {
                i = two - 1;

                next = 0;
                base = 0;
                two = -1;
                start = false;
                end = false;
                head = 0;
            }

        } else {
            if(two > 0) {
                i = two - 1;

                next = 0;
                base = 0;
                two = -1;
                start = false;
                end = false;
                head = 0;
            } else {
                if(end || !start) {
                    if(input.charAt(i) == input.charAt(0)) i--;

                    next = 0;
                    base = 0;
                    two = -1;
                    start = false;
                    end = false;
                    head = 0;
                } else {
                    i--;

                    next = next - tail;
                    base = base -1;
                    two = -1;
                    start = base==0 ? false : true;
                    end = false;
                    //head = 0;
                }                   
            }
        }
    }
    count = count + input.length();
    return count;
}

Ответ 7

С моей точки зрения, какой бы метод вы ни выбрали для реализации, он, как правило, будет иметь свой худший случай. Разница в том, что производительность в худшем случае.
Например, я протестировал метод isnot2bad, свою первую реализацию (oneTry) и мою вторую реализацию (secondTry) на моем ПК.
Результаты тестов для наихудшего случая:
isnot2bad: ~ 330s (2 * 10 ^ 5), ~ 74s (10 ^ 5), ~ 0,8 (10 ^ 4), ~ 0,01 (10 ^ 3)
моя первая реализация (oneTry): ~ 200s (2 * 10 ^ 5), ~ 45s (10 ^ 5), ~ 0,5s (10 ^ 4), ~ 0,01 (10 ^ 3)
моя вторая реализация (secondTry): ~ 4s (10 ^ 6), ~ 0.4s (10 ^ 5), ~ 0.05s (10 ^ 4), ~ 0.007 (10 ^ 3)

Из результатов теста видно, что наихудшее время исполнения для "secondTry" почти линейно с длиной строки, а другие почти квадратные с длиной строки.

Идея реализации secondTry выглядит так:
Для любого ввода строки T (T0... Tn-1, len = n), общее значение сходства строки (St) представляет собой сумму каждого отдельного char значение подобия ( Si) среди строки S.
    например: St = S0 +... + Si +... + Sn-1
Очевидно, общее число T0 в подстроке [T0... Ti] >= Si >= 1
Точное значение Si равно общему числу T0 в подстроке [T0... Ti], которое продолжает соответствовать Ti.
Например: T = "aabaab", тогда T2 = 'b', только T0 ('a') может продолжать T2, а T1 ('a') не может продолжаться до T2. Следовательно, S2 = 1 Поэтому нам нужно отслеживать, что T0 продолжается (если да, сохраните его в массиве, если нет, удалите его из массива). Тогда легко вычислить каждое подобие Ti.
Между тем, чтобы улучшить производительность, нам не нужно проверять каждый cononnuing T0. Соответственно, для некоторых T0 они могут быть объединены вместе.
Потому что они принадлежат к шаблону повторения (это может быть длинный шаблон или короткий шаблон).
Например:
  ababababab...: T0, T2, T4, T6... могут быть объединены вместе как целое.
  aaaaaaaaaa...: T0, T1, T2, T3... могут быть объединены вместе как целое.
  aaaabaaaabaaaab...:
      T0, T5, T10, T15... могут быть объединены вместе как единое целое.
      T1, T2, T3 можно комбинировать вместе.       T6, T7, T8 можно комбинировать вместе.       ...

Детальный код реализации показан ниже. Надеюсь, кто-то может опубликовать свои лучшие результаты и результаты теста для этой темы. Спасибо.

    public static List<ANode> anodes = null;
    public static List<ANode> tnodes = null;
    public static void checkANodes(CharSequence input, int num) {
        tnodes = new Vector<ANode>(); 
        for(int i=anodes.size()-1; i>=0; i--) {
            ANode anode = anodes.get(i);
            if(input.charAt(num) == input.charAt(num-anode.pos)) {
                tnodes.add(anode);
            }else {
                if(tnodes.size() > 0) {
                    // ok to do the changes
                    ANode after = tnodes.get(tnodes.size()-1);
                    tnodes.remove(after);
                    if(after.c > 1) {
                        tnodes.add(new ANode(after.pos + after.shift, after.shift ,after.c-1)); 
                        tnodes.add(new ANode(after.pos, after.pos-anode.pos + anode.shift,1));
                    }else {
                        tnodes.add(new ANode(after.pos, after.pos-anode.pos + anode.shift,1));  
                    }
                }
            }
        }

        anodes.clear();
        for(int i=tnodes.size() - 1; i >= 0; i--) {
            anodes.add(tnodes.get(i));
        }
    }

    public static int secondTry(CharSequence input) {
        anodes = new Vector<ANode>();

        int start = 0;
        for (int i = 1; i < input.length(); i++) {
            if (input.charAt(i) == input.charAt(0)) {
                start = i;
                break;
            }
        }

        int count = 0;
        int base = 0;
        for (int i = start; i < input.length(); i++) {
            checkANodes(input, i);
            if(input.charAt(0) == input.charAt(i)) {
                if(anodes.size() == 0) {
                    anodes.add(new ANode(i,  i, 1));
                }else {
                    ANode last = anodes.get(anodes.size()-1);
                    int shift = i - last.pos;
                    int mod = shift % last.shift;
                    if(mod == 0) {
                        last.c++;
                    }else {
                        anodes.add(new ANode(i, mod, 1));
                    }
                }
            }

            base = 0;
            for(ANode anode : anodes) {
                base = base + anode.c;
            }           
            count = count + base;
        }

        count = count + input.length();
        return count;
    }

public class ANode {
    public int pos = 0;
    public int c = 1;
    public int shift = 0;

    public ANode(int pos, int shift, int c) {
        this.pos = pos;
        this.shift = shift;
        this.c = c;
    }
}