la única subcadena más pequeña para cada cadena en una matriz

Question

(estoy escribiendo esto en el contexto de JavaScript, pero aceptará una respuesta correcta mediante algoritmos en cualquier idioma)

¿Cómo se encuentra el la subcadena más corta de cada elemento en una matriz de cadenas donde la subcadena NO está contenida en ninguno de los otros elementos, ignorando el caso?

Supongamos que tengo una matriz de entrada, tales como:

var names = ["Anne", "Anthony", "LouAnn", "Kant", "Louise", "ark"]; 

La salida debe ser algo como:

var uniqueNames = ["ne", "h", "ua", "ka", "i", "r"]; 

Para mis propósitos, se puede asumir con seguridad que ningún elemento será totalmente contenido dentro de otro elemento

Mis Pensamientos:
Parece que uno podría probablemente la fuerza bruta de este, a lo largo de las líneas de:

var names = ["Anne", "Anthony", "LouAnn", "Kant", "Louise", "ark"]; 
var uniqueNames = [], nameInd, windowSize, substrInd, substr, otherNameInd, foundMatch; 
// For each name 
for (nameInd = 0; nameInd < names.length; nameInd++) 
{ 
    var name = names[nameInd]; 
    // For each possible substring length 
    windowLoop: 
    for (windowSize = 1; windowSize <= name.length; windowSize++) 
    { 
     // For each starting index of a substring 
     for (substrInd = 0; substrInd <= name.length-windowSize; substrInd++) 
     { 
      substr = name.substring(substrInd,substrInd+windowSize).toLowerCase(); 
      foundMatch = false; 
      // For each other name 
      for (otherNameInd = 0; otherNameInd < names.length; otherNameInd++) 
      { 
       if (nameInd != otherNameInd && names[otherNameInd].toLowerCase().indexOf(substr) > -1) 
       { 
        foundMatch = true; 
        break; 
       } 
      } 

      if (!foundMatch) 
      { 
       // This substr works! 
       uniqueNames[nameInd] = substr; 
       break windowLoop; 
      } 
     } 
    } 
} 

Pero tengo que imaginar que hay una solución más elegante usando tries/árboles prefijo, sufijo arrays, o algo tan interesante como eso.

Editar: Creo que esta es la forma de la respuesta seleccionada tomaría mediante programación en JavaScript:

var names = ["Anne", "Anthony", "LouAnn", "Kant", "Louise", "ark"]; 
var uniqueNames = [], permutations = {}, permutation, nameInd, windowSize, substrInd, substr; 

// For each name 
for (nameInd = 0; nameInd < names.length; nameInd++) 
{ 
    var name = names[nameInd]; 
    // For each possible substring length 
    windowLoop: 
    for (windowSize = 1; windowSize <= name.length; windowSize++) 
    { 
     // For each starting index of a substring 
     for (substrInd = 0; substrInd <= name.length-windowSize; substrInd++) 
     { 
      substr = name.substring(substrInd,substrInd+windowSize).toLowerCase(); 
      permutations[substr] = (typeof permutations[substr] === "undefined")?nameInd:-1; 
     } 
    } 
} 

for (substr in permutations) 
{ 
    permutation = permutations[substr]; 
    if (permutation !== -1 && ((typeof uniqueNames[permutation] === "string" && substr.length < uniqueNames[permutation].length) || typeof uniqueNames[permutation] === "undefined")) 
    { 
     uniqueNames[permutation] = substr; 
    } 
} 

Answer 1

Say N es el número de cadenas y L es la longitud máxima de cadena. Estás haciendo hasta N*L*L*N iteraciones.

Solo puedo mejorarlo cambiando una iteración por memoria extra. Para cada posible longitud subcadena (L iteraciones),

• enumerar todas las subcadenas de que la longitud en cada nombre (N*L), y almacenarlo entre con el índice de nombre en una tabla hash (1). Si ya hay un índice para esta subcadena, usted sabe que no funcionará, luego reemplaza el índice con algún valor especial, como -1.

• caminar por la tabla hash, recogiendo subseries para los que el índice no es -1 - que son las respuestas para sus correspondientes índices, pero sólo usarlos si que los nombres no tienen ya una respuesta más corto de una iteración anterior

El uso de memoria se puede reducir en gran medida almacenando la referencia en una cadena existente en lugar de copiar subcadenas.

Answer 2

Este problema se puede resolver en O (N * L * L * L) complejidad. El enfoque utilizará sufijos de prueba. Cada nodo del trie también almacenará el recuento de prefijos que se referirá al número de veces que la subcadena formada al atravesar ese nodo desde la raíz ha aparecido en todos los sufijos insertados hasta ahora.

Construiremos N + 1 de intentos.El primer trie será global e insertaremos todos los sufijos de todas las cadenas N. Los siguientes intentos de N serán locales para cada una de las cadenas N que contengan los sufijos correspondientes.

Este proceso de preprocesamiento de intentos de construcción se realizará en O (N * L * L).

Ahora una vez que se han construido los intentos, para cada cadena, podemos comenzar a buscar el número de veces que ha ocurrido una subcadena (comenzando desde la longitud mínima) en el trie global y el trie correspondiente a esa cadena. Si es igual en ambos, implica que no está incluido en ninguna otra cadena excepto en sí misma. Esto se puede lograr en O (N * L * L * L). La complejidad puede explicarse como N para cada cadena, L * L para considerar cada subcadena y L para realizar una consulta en el trie.

Answer 3

Si construye un sufijo generalizado, solo necesita encontrar el punto más bajo en el que un infijo de cada cadena se bifurca de los infijos de las otras cadenas, y lleve la etiqueta a ese punto de ramificación más una "distinción" personaje. El truco es que tiene que haber un personaje extra (podría estar bifurcando solo en el metacarácter pegado al final de cada cuerda), y el punto de bifurcación podría no llevar a una hoja, podría conducir a un subárbol con hojas todas de la misma cuerda (por lo que se deben considerar los nodos internos).

Para cada cadena S, encuentre el nodo N más superficial (por profundidad de etiqueta principal) que solo contiene hojas de S y cuya etiqueta de borde contiene al menos un carácter. La etiqueta de ruta de raíz al padre de N, más un carácter de la etiqueta de borde que conduce a N, es el infijo más corto de S no encontrado en otras cadenas.

Creo que el etiquetado de los nodos que solo contienen hojas de una cadena se puede hacer durante la construcción o mediante el escaneo O (N) de la GST; entonces es una cuestión simple escanear el árbol final y mantener un mínimo de funcionamiento para cada cadena. Entonces todo es O (N).

(edit - No puedo responder a los comentarios aún)

Para aclarar, cada sufijo en un árbol de sufijos tiene un nodo en el que se ramifica a partir de los otros sufijos; el objetivo aquí es encontrar el sufijo/a para cada cadena que se bifurca de los sufijos de todas las demás cadenas con la profundidad mínima, según lo medido por la etiqueta de ruta a ese nodo. Todo lo que necesitamos es un personaje extra después de ese punto para tener una subcadena que no aparece en ninguna otra cadena.

Ejemplo:

Cuerdas: abbc, abc

Usando el algoritmo de Ukonnen, después de la primera cuerda que tenemos un árbol de sufijos de sólo los sufijos de esa cadena; Voy a etiquetarlos con [1] aquí:

abbc[1] 
b 
bc[1] 
c[1] 
c[1] 

A continuación insertamos de cuerda de 2 sufijos:

ab 
    bc[1] 
    c[2] 
b 
bc[1] 
c 
    [1] 
    [2] 
c 
[1] 
[2] 

Ahora queremos encontrar la cadena más corta que conduce a una rama con solamente [1] está debajo de eso; podemos hacerlo mediante el escaneo de todo el [1] 's y mirando a sus padres inmediatos, que voy a enumerar aquí por la ruta de etiquetas, además de uno de los personajes (que voy a utilizar más adelante):

abbc: abb 
bbc: bb 
bc: bc[1] 
c: c[1] 

en cuenta que yo He incluido [1] ya que es el metacarácter que distingue los sufijos de lo contrario idénticos de [1] y [2]. Esto es útil cuando identificamos subcadenas que se repiten en varias cadenas, pero no es útil para nuestro problema, ya que si eliminamos [1] también terminamos con una cadena que aparece en [2], es decir, no es un candidato.

Ahora, ninguna de las etiquetas de la derecha aparece en ninguna otra cadena, por lo que elegimos la más corta, sin incluir un metacarácter, que es bb.

Del mismo modo, la segunda cadena tiene estos candidatos:

abc: abc 
bc: bc[2] 
c: c[2] 

Sólo uno no tiene un meta al final, así que tenemos que ir con ABC.

Mi punto final es que este hallazgo mínimo por cadena no tiene que suceder uno a la vez; el GST puede escanearse una vez para etiquetar los nodos como si contiene hojas de una cadena ([1], [2], ... [n]) o "mixta", y luego las cadenas mínimas no compartidas por cadena (lo haría llamar a estos "infijos distintivos") se puede calcular en una sola pasada también.