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

Самый эффективный способ поиска неизвестных шаблонов в строке?

Я пытаюсь найти шаблоны, которые:

  • происходит более одного раза
  • длиной более 1 символа
  • не являются подстроками любого другого известного шаблона

не зная ни одного из шаблонов, которые могут возникнуть.

Например:

  • Строка "мальчик упала на звонок" вернет 'ell', 'the b', 'y '.
  • Строка "мальчик упал у колокола, мальчик упал на звонок" вернул 'the boy fell by the bell'.

Использование двойных for-loops, это может быть грубо принудительно очень неэффективно:

ArrayList<String> patternsList = new ArrayList<>();
int length = string.length();
for (int i = 0; i < length; i++) {
    int limit = (length - i) / 2;
    for (int j = limit; j >= 1; j--) {
        int candidateEndIndex = i + j;
        String candidate = string.substring(i, candidateEndIndex);

        if(candidate.length() <= 1) {
            continue;
        }

        if (string.substring(candidateEndIndex).contains(candidate)) {
            boolean notASubpattern = true;
            for (String pattern : patternsList) {
                if (pattern.contains(candidate)) {
                    notASubpattern = false;
                    break;
                }
            }

            if (notASubpattern) {
                patternsList.add(candidate);
            }
        }
    }
}

Тем не менее, это невероятно медленно при поиске больших строк с тоннами шаблонов.

4b9b3361

ОТВЕТЫ

Ответ 1

Вы можете построить дерево суффиксов для своей строки в линейном времени:  https://en.wikipedia.org/wiki/Suffix_tree

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

Ответ 2

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

Например, в строке "мальчик упал на звонок, мальчик упал на звонок", используя 6-грамму, найдет подстроку "мальчик упал на звонок". Запись хэш-таблицы с этой подстрокой будет иметь счет 2, потому что она произошла дважды в строке. Изменение количества слов в n-графе поможет вам обнаружить различные шаблоны в строке.

Dictionary<string, int>dict = new Dictionary<string, int>();
int count = 0;
int ngramcount = 6;
string substring = "";

// Add entries to the hash table
while (count < str.length) {
    // copy the words into the substring
    int i = 0;
    substring = "";
    while (ngramcount > 0 && count < str.length) {
        substring[i] = str[count];
        if (str[i] == ' ')
            ngramcount--;
        i++;
        count++;
    }
    ngramcount = 6;
    substring.Trim();  // get rid of the last blank in the substring
    // Update the dictionary (hash table) with the substring
    if (dict.Contains(substring)) {  // substring is already in hash table so increment the count
        int hashCount = dict[substring];
        hashCount++;
        dict[substring] = hashCount;
    }
    else
        dict[substring] = 1;
}

// Find the most commonly occurrring pattern in the string
// by searching the hash table for the greatest count.
int maxCount = 0;
string mostCommonPattern = "";
foreach (KeyValuePair<string, int> pair in dict) {
    if (pair.Value > maxCount) {
        maxCount = pair.Value;
        mostCommonPattern = pair.Key;
    }
}

Ответ 3

Я написал это просто для удовольствия. Надеюсь, я правильно понял проблему, это действительно и достаточно быстро; если нет, пожалуйста, будьте легко на меня:) Я мог бы оптимизировать его немного больше, я думаю, если кто-то сочтет это полезным.

private static IEnumerable<string> getPatterns(string txt)
{
    char[] arr = txt.ToArray();
    BitArray ba = new BitArray(arr.Length);
    for (int shingle = getMaxShingleSize(arr); shingle >= 2; shingle--)
    {
        char[] arr1 = new char[shingle];
        int[] indexes = new int[shingle];
        HashSet<int> hs = new HashSet<int>();
        Dictionary<int, int[]> dic = new Dictionary<int, int[]>();
        for (int i = 0, count = arr.Length - shingle; i <= count; i++)
        {
            for (int j = 0; j < shingle; j++)
            {
                int index = i + j;
                arr1[j] = arr[index];
                indexes[j] = index;
            }
            int h = getHashCode(arr1);
            if (hs.Add(h))
            {
                int[] indexes1 = new int[indexes.Length];
                Buffer.BlockCopy(indexes, 0, indexes1, 0, indexes.Length * sizeof(int));
                dic.Add(h, indexes1);
            }
            else
            {
                bool exists = false;
                foreach (int index in indexes)
                    if (ba.Get(index))
                    {
                        exists = true;
                        break;
                    }
                if (!exists)
                {
                    int[] indexes1 = dic[h];
                    if (indexes1 != null)
                        foreach (int index in indexes1)
                            if (ba.Get(index))
                            {
                                exists = true;
                                break;
                            }
                }
                if (!exists)
                {
                    foreach (int index in indexes)
                        ba.Set(index, true);
                    int[] indexes1 = dic[h];
                    if (indexes1 != null)
                        foreach (int index in indexes1)
                            ba.Set(index, true);
                    dic[h] = null;
                    yield return new string(arr1);
                }
            }
        }
    }
}
private static int getMaxShingleSize(char[] arr)
{            
    for (int shingle = 2; shingle <= arr.Length / 2 + 1; shingle++)
    {
        char[] arr1 = new char[shingle];
        HashSet<int> hs = new HashSet<int>();
        bool noPattern = true;
        for (int i = 0, count = arr.Length - shingle; i <= count; i++)
        {
            for (int j = 0; j < shingle; j++)
                arr1[j] = arr[i + j];
            int h = getHashCode(arr1);
            if (!hs.Add(h))
            {
                noPattern = false;
                break;
            }
        }
        if (noPattern)
            return shingle - 1;
    }
    return -1;
}
private static int getHashCode(char[] arr)
{
    unchecked
    {
        int hash = (int)2166136261;
        foreach (char c in arr)
            hash = (hash * 16777619) ^ c.GetHashCode();
        return hash;
    }
}

Edit
У моего предыдущего кода серьезные проблемы. Это лучше:

private static IEnumerable<string> getPatterns(string txt)
{
    Dictionary<int, int> dicIndexSize = new Dictionary<int, int>();
    for (int shingle = 2, count0 = txt.Length / 2 + 1; shingle <= count0; shingle++)
    {   
        Dictionary<string, int> dic = new Dictionary<string, int>();
        bool patternExists = false;
        for (int i = 0, count = txt.Length - shingle; i <= count; i++)
        {
            string sub = txt.Substring(i, shingle);
            if (!dic.ContainsKey(sub))
                dic.Add(sub, i);
            else
            {   
                patternExists = true;
                int index0 = dic[sub];
                if (index0 >= 0)
                {
                    dicIndexSize[index0] = shingle;
                    dic[sub] = -1;
                }
            }
        }
        if (!patternExists)
            break;
    }
    List<int> lst = dicIndexSize.Keys.ToList();
    lst.Sort((a, b) => dicIndexSize[b].CompareTo(dicIndexSize[a]));
    BitArray ba = new BitArray(txt.Length);
    foreach (int i in lst)
    {
        bool ok = true;
        int len = dicIndexSize[i];
        for (int j = i, max = i + len; j < max; j++)
        {
            if (ok) ok = !ba.Get(j);
            ba.Set(j, true);
        }
        if (ok)
            yield return txt.Substring(i, len);
    }
}

Текст эта книга заняла 3.4 секунды на моем компьютере.

Ответ 4

Суффиксные массивы - правильная идея, но там нетривиальная часть отсутствует, а именно, определение того, что известно в литературе как "супермаксимальные повторы". Здесь репозиторий GitHub с рабочим кодом: https://github.com/eisenstatdavid/commonsub. Конструкция массива суффикса использует библиотеку SAIS, представленную в виде подмодуля. Супермаксимальные повторы найдены с использованием скорректированной версии псевдокода от findsmaxr в Эффективное повторное обнаружение через массивы суффиксов (Бехера – Deymonnaz – Heiber).

static void FindRepeatedStrings(void) {
  // findsmaxr from https://arxiv.org/pdf/1304.0528.pdf
  printf("[");
  bool needComma = false;
  int up = -1;
  for (int i = 1; i < Len; i++) {
    if (LongCommPre[i - 1] < LongCommPre[i]) {
      up = i;
      continue;
    }
    if (LongCommPre[i - 1] == LongCommPre[i] || up < 0) continue;
    for (int k = up - 1; k < i; k++) {
      if (SufArr[k] == 0) continue;
      unsigned char c = Buf[SufArr[k] - 1];
      if (Set[c] == i) goto skip;
      Set[c] = i;
    }
    if (needComma) {
      printf("\n,");
    }
    printf("\"");
    for (int j = 0; j < LongCommPre[up]; j++) {
      unsigned char c = Buf[SufArr[up] + j];
      if (iscntrl(c)) {
        printf("\\u%.4x", c);
      } else if (c == '\"' || c == '\\') {
        printf("\\%c", c);
      } else {
        printf("%c", c);
      }
    }
    printf("\"");
    needComma = true;
  skip:
    up = -1;
  }
  printf("\n]\n");
}

Вот пример вывода текста первого абзаца:

Davids-MBP:commonsub eisen$ ./repsub input
["\u000a"
," S"
," as "
," co"
," ide"
," in "
," li"
," n"
," p"
," the "
," us"
," ve"
," w"
,"\""
,"&ndash;"
,"("
,")"
,". "
,"0"
,"He"
,"Suffix array"
,"`"
,"a su"
,"at "
,"code"
,"com"
,"ct"
,"do"
,"e f"
,"ec"
,"ed "
,"ei"
,"ent"
,"ere a "
,"find"
,"her"
,"https://"
,"ib"
,"ie"
,"ing "
,"ion "
,"is"
,"ith"
,"iv"
,"k"
,"mon"
,"na"
,"no"
,"nst"
,"ons"
,"or"
,"pdf"
,"ri"
,"s are "
,"se"
,"sing"
,"sub"
,"supermaximal repeats"
,"te"
,"ti"
,"tr"
,"ub "
,"uffix arrays"
,"via"
,"y, "
]

Ответ 5

Я бы использовал алгоритм Кнута-Морриса-Пратта (линейная временная сложность O (n)), чтобы найти подстроки. Я попытался бы найти самый большой шаблон подстроки, удалить его из входной строки и попытаться найти вторую по величине и так далее. Я бы сделал что-то вроде этого:

string pattern = input.substring(0,lenght/2);
string toMatchString = input.substring(pattern.length, input.lenght - 1);

List<string> matches = new List<string>();

while(pattern.lenght > 0)
{
    int index = KMP(pattern, toMatchString);
    if(index > 0)
    {
        matches.Add(pattern);

        // remove the matched pattern occurences from the input string
        // I would do something like this:
        // 0 to pattern.lenght gets removed
        // check for all occurences of pattern in toMatchString and remove them
        // get the remaing shrinked input, reassign values for pattern & toMatchString
        // keep looking for the next largest substring
    }
    else
    {
        pattern = input.substring(0, pattern.lenght - 1);
        toMatchString = input.substring(pattern.length, input.lenght - 1);
    }
}

Где KMP реализует алгоритм Кнута-Морриса-Пратта. Вы можете найти его реализацию Java в Github или Princeton или напишите сами.

PS: Я не кодирую на Java, и я быстро пытаюсь, чтобы моя первая щедрость скоро закрылась. Поэтому, пожалуйста, не давайте мне палку, если я пропустил что-то тривиальное или сделал ошибку +/- 1.