utilizar - validar alfanumerico java

¿La forma más eficiente de buscar patrones desconocidos en una cadena?

Question

Estoy tratando de encontrar patrones que:

• ocurrir mas de una vez
• tienen más de 1 carácter
• No son subcadenas de ningún otro patrón conocido.

Sin conocer ninguno de los patrones que puedan ocurrir.

Por ejemplo:

• La cadena "el niño cayó junto a la campana" devolvería ''ell'', ''the b'', ''y '' .
• La cuerda "el niño cayó junto a la campana, el niño cayó junto a la campana" devolvería ''the boy fell by the bell'' .

Usando dobles bucles for, se puede forzar bruta de manera muy ineficiente:

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);
            }
        }
    }
}

Sin embargo, esto es increíblemente lento cuando se buscan cadenas grandes con toneladas de patrones.

Answer 1

He escrito esto solo por diversión. Espero haber entendido el problema correctamente, esto es válido y lo suficientemente rápido; Si no, por favor, sea fácil para mí :) Podría optimizarlo un poco más, supongo, si alguien lo encuentra útil.

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;
    }
}

Editar
Mi código anterior tiene serios problemas. Éste es mejor:

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);
    }
}

El texto en este libro tomó 3.4sec en mi computadora.

Answer 2

Las matrices de sufijos son la idea correcta, pero falta una pieza no trivial, es decir, identificar lo que se conoce en la literatura como "repeticiones supermaximas". Aquí hay un repositorio de GitHub con código de trabajo: https://github.com/eisenstatdavid/commonsub . La construcción de matrices de sufijos utiliza la biblioteca SAIS, que se vende como un submódulo. Las repeticiones supermaximas se encuentran utilizando una versión corregida del pseudocódigo de findsmaxr en la búsqueda eficiente de repeticiones a través de matrices de sufijos (Becher – 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");
}

Aquí hay una salida de muestra en el texto del primer párrafo:

Davids-MBP:commonsub eisen$ ./repsub input
["/u000a"
," S"
," as "
," co"
," ide"
," in "
," li"
," n"
," p"
," the "
," us"
," ve"
," w"
,"/""
,"–"
,"("
,")"
,". "
,"0"
,"He"
,"Suffix array"
,"`"
,"a su"
,"at "
,"code"
,"com"
,"ct"
,"do"
,"e f"
,"ec"
,"ed "
,"ei"
,"ent"
,"ere''s 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, "
]

Answer 3

Puede crear un árbol de sufijos para su cadena en tiempo lineal: https://en.wikipedia.org/wiki/Suffix_tree

Los patrones que busca son las cadenas correspondientes a los nodos internos que solo tienen hijos de hoja.

Answer 4

Puedes usar n-grams para encontrar patrones en una cadena. Tomaría O (n) tiempo para escanear la cadena de n-gramas. Cuando encuentre una subcadena utilizando un n-gramo, póngala en una tabla hash con un recuento de cuántas veces se encontró esa subcadena en la cadena. Cuando haya terminado de buscar n-gramas en la cadena, busque en la tabla hash los conteos mayores que 1 para encontrar patrones recurrentes en la cadena.

Por ejemplo, en la cadena "el niño cayó junto a la campana, el niño cayó junto a la campana" utilizando 6 gramos encontrará la subcadena "el niño cayó junto a la campana". Una entrada de tabla hash con esa subcadena tendrá un conteo de 2 porque ocurrió dos veces en la cadena. Variar el número de palabras en el n-gramo te ayudará a descubrir diferentes patrones en la cadena.

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;
    }
}

Answer 5

Usaría el algoritmo de Knuth – Morris – Pratt (complejidad de tiempo lineal O (n) ) para encontrar subcadenas. Intentaría encontrar el patrón de subcadena más grande, eliminarlo de la cadena de entrada e intentar encontrar el segundo más grande y así sucesivamente. Haría algo como esto:

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);
    }
}

Donde KMP implementa el algoritmo de Knuth-Morris-Pratt. Puedes encontrar las implementaciones de Java en Github o Princeton o escribirlas tú mismo.

PD: no codifico en Java y es un intento rápido de que mi primera recompensa esté a punto de cerrarse pronto. Así que, por favor, no me des el palo si me perdí algo trivial o cometí un error de +/- 1.