Dado un conjunto de 50k cadenas, necesito encontrar todos los pares (s, t), de modo que s, t y s + t estén todos contenidos en este conjunto.

Lo que he intentado

, hay una restricción adicional: s.length() >= 4 && t.length() >= 4. Esto hace posible agrupar las cadenas por prefijos de longitud 4 y, por separado, sufijos. Luego, para cada cadena composed de longitud de al menos 8, busco el conjunto de candidatos para s utilizando los primeros cuatro caracteres de composed y el conjunto de candidatos para t utilizando sus últimos cuatro caracteres. Esto funciona, pero necesita mirar 30 millones de pares de candidatos (s, t) para encontrar los resultados de 7k.

Este número sorprendentemente alto de candidatos proviene del hecho de que la cadena son palabras (en su mayoría alemanas) de un vocabulario limitado y la palabra comienza y termina a menudo igual. Todavía es mucho mejor que probar todos los pares de 2.5G, pero mucho peor de lo que esperaba.

Lo que necesito

Como la restricción adicional puede caerse y el conjunto crecerá, estoy buscando un mejor algoritmo.

La pregunta "faltante"

Hubo quejas de que no hice una pregunta. Entonces, el signo de interrogación faltante está al final de la siguiente oración. ¿Cómo se puede hacer esto de manera más eficiente, idealmente sin usar la restricción?

4
maaartinus 10 sep. 2018 a las 07:42

4 respuestas

La mejor respuesta

Algoritmo 1: Prueba de pares, no individuales

Una forma podría ser, en lugar de trabajar desde todos los pares posibles hasta todas las cadenas compuestas posibles que contengan esos pares, trabajar desde todas las cadenas compuestas posibles y ver si contienen pares. Esto cambia el problema de las búsquedas de n^2 (donde n es el número de cadenas> = 4 caracteres) a las búsquedas de m * n (donde m es la longitud promedio de todas las cadenas> = 8 caracteres, menos 7, y n es ahora el número de cadenas> = 8 caracteres). Aquí hay una implementación de eso:

int minWordLength = 4;
int minPairLength = 8;

Set<String> strings = Stream
   .of(
      "a", "abc", "abcdef", "def", "sun", "sunshine", "shine",
      "bear", "hug", "bearhug", "cur", "curlique", "curl",
      "down", "downstream", "stream"
   )
   .filter(s -> s.length() >= minWordLength)
   .collect(ImmutableSet.toImmutableSet());

strings
   .stream()
   .filter(s -> s.length() >= minPairLength)
   .flatMap(s -> IntStream
      .rangeClosed(minWordLength, s.length() - minWordLength)
      .mapToObj(splitIndex -> ImmutableList.of(
         s.substring(0, splitIndex),
         s.substring(splitIndex)
      ))
      .filter(pair ->
          strings.contains(pair.get(0))
          && strings.contains(pair.get(1))
      )
   )
   .map(pair ->
      pair.get(0) + pair.get(1) + " = " + pair.get(0) + " + " + pair.get(1)
   )
   .forEach(System.out::println);

Da el resultado:

downstream = down + stream

Esto tiene una complejidad algorítmica promedio de m * n como se muestra arriba. En efecto, O(n). En el peor de los casos, O(n^2). Consulte tabla hash para obtener más información sobre la complejidad algorítmica.

Explicación

  1. Coloque todas las cadenas de cuatro o más caracteres en un conjunto de hash (lo que requiere una complejidad O (1) promedio para la búsqueda). Usé Guava's ImmutableSet por conveniencia. Usa lo que quieras.
  2. filter: Restrinja solo a los elementos que tienen ocho o más caracteres de longitud, lo que representa a nuestros candidatos para ser una composición de otras dos palabras en la lista.
  3. flatMap: Para cada candidato, calcule todos los pares posibles de sub-palabras, asegurándose de que cada una tenga al menos 4 caracteres. Como puede haber más de un resultado, esta es en efecto una lista de listas, así que aplánelo en una lista de profundidad única.
    1. rangeClosed: genera todos los enteros que representan el número de caracteres que estarán en la primera palabra del par que verificaremos.
    2. mapToObj: use cada número entero combinado con nuestra cadena candidata para generar una lista de dos elementos (en el código de producción probablemente desearía algo más claro, como una clase de valor de dos propiedades o una clase existente apropiada) .
    3. filter: restrinja a solo pares donde ambos estén en la lista.
  4. map: Bastante un poco los resultados.
  5. forEach: Salida a la consola.

Elección de algoritmo

Este algoritmo está ajustado a palabras que son mucho más cortas que el número de elementos en la lista. Si la lista fuera muy corta y las palabras fueran muy largas, volver a una tarea de composición en lugar de una tarea de descomposición funcionaría mejor. Dado que la lista tiene un tamaño de 50,000 cadenas, y las palabras alemanas, aunque largas, es muy poco probable que excedan los 50 caracteres, ese es un factor de 1: 1000 a favor de este algoritmo.

Si, por otro lado, tuviera 50 cadenas que tenían una longitud promedio de 50,000 caracteres, un algoritmo diferente sería mucho más eficiente.

Algoritmo 2: ordenar y mantener una lista de candidatos

Un algoritmo en el que pensé por un momento fue ordenar la lista, sabiendo que si una cadena representa el comienzo de un par, todas las cadenas candidatas que podrían ser uno de sus pares serán inmediatamente posteriores en orden, entre el conjunto de elementos que comienzan con esa cadena. Ordenando mis datos engañosos arriba y agregando algunos factores de confusión (downer, downs, downregulate) obtenemos:

a
abc
abcdef
bear
bearhug
cur
curl
curlique
def
down ---------\
downs         |
downer        | not far away now!
downregulate  |
downstream ---/
hug
shine
stream
sun
sunshine

Por lo tanto, si se mantuviera un conjunto continuo de todos los elementos para verificar, podríamos encontrar compuestos candidatos en un tiempo esencialmente constante por palabra, luego investigar directamente en una tabla hash la palabra restante:

int minWordLength = 4;

Set<String> strings = Stream
   .of(
      "a", "abc", "abcdef", "def", "sun", "sunshine", "shine",
      "bear", "hug", "bearhug", "cur", "curlique", "curl",
      "down", "downs", "downer", "downregulate", "downstream", "stream")
   .filter(s -> s.length() >= minWordLength)
   .collect(ImmutableSet.toImmutableSet());

ImmutableList<String> orderedList = strings
   .stream()
   .sorted()
   .collect(ImmutableList.toImmutableList());
List<String> candidates = new ArrayList<>();
List<Map.Entry<String, String>> pairs = new ArrayList<>();

for (String currentString : orderedList) {
   List<String> nextCandidates = new ArrayList<>();
   nextCandidates.add(currentString);
   for (String candidate : candidates) {
      if (currentString.startsWith(candidate)) {
         nextCandidates.add(candidate);
         String remainder = currentString.substring(candidate.length());
         if (remainder.length() >= minWordLength && strings.contains(remainder)) {
            pairs.add(new AbstractMap.SimpleEntry<>(candidate, remainder));
         }
      }
   }
   candidates = nextCandidates;
}
pairs.forEach(System.out::println);

Resultado:

down=stream

La complejidad algorítmica en este caso es un poco más complicada. La parte de búsqueda creo que es O(n) promedio, con O(n^2) el peor de los casos. La parte más costosa podría ser la clasificación, que depende del algoritmo utilizado y las características de los datos no clasificados. Entonces use este con un grano de sal, pero tiene posibilidad. Me parece que esto va a ser mucho menos costoso que construir un Trie a partir de un enorme conjunto de datos, porque solo lo prueba una vez de manera integral y no obtiene ninguna amortización del costo de construcción.

Además, esta vez elegí un Map.Entry para mantener el par. Es completamente arbitrario cómo lo haces. Hacer una clase personalizada Pair o usar alguna clase Java existente estaría bien.

5
ErikE 13 sep. 2018 a las 14:30

No estoy seguro de si esto es mejor que su solución, pero creo que vale la pena intentarlo.

Cree dos Intentos, uno con los candidatos en orden normal y el otro con las palabras invertidas.

Camina hacia adelante Trie desde la profundidad 4 hacia adentro y usa el resto de la hoja para determinar el sufijo (o algo así) y búscalo hacia atrás Trie.

He publicado una implementación Trie en el pasado aquí https://stackoverflow.com/a/9320920/823393.

0
OldCurmudgeon 10 sep. 2018 a las 06:02

Una posible solución podría ser esta. Comienzas con la primera cadena como prefijo y la segunda cadena como sufijo. Atraviesas cada cuerda. Si la cadena comienza con la primera cadena, verifica si termina en la segunda cadena. Y sigue hasta el final. Para ahorrar algo de tiempo antes de verificar si las letras son las mismas, puede hacer una verificación de longitud. Es más o menos lo que hizo, pero con esta verificación de longitud adicional, puede recortar algunas. Esa es mi opinión al menos.

0
The Mods Hunter 10 sep. 2018 a las 04:56

Puede mejorar la respuesta de Erik evitando la mayor parte de la creación de sub - String usando CharBuffer vistas y alterando su posición y límite:

Set<CharBuffer> strings = Stream.of(
    "a", "abc", "abcdef", "def", "sun", "sunshine", "shine",
    "bear", "hug", "bearhug", "cur", "curlique", "curl",
    "down", "downstream", "stream"
 )
.filter(s -> s.length() >= 4) // < 4 is irrelevant
.map(CharBuffer::wrap)
.collect(Collectors.toSet());

strings
    .stream()
    .filter(s -> s.length() >= 8)
    .map(CharBuffer::wrap)
    .flatMap(cb -> IntStream.rangeClosed(4, cb.length() - 4)
        .filter(i -> strings.contains(cb.clear().position(i))&&strings.contains(cb.flip()))
        .mapToObj(i -> cb.clear()+" = "+cb.limit(i)+" + "+cb.clear().position(i))
    )
    .forEach(System.out::println);

Este es el mismo algoritmo, por lo tanto, no cambia la complejidad del tiempo, a menos que incorpore los costos de copia de datos de caracteres ocultos, lo que sería otro factor (multiplicado por la longitud promedio de la cadena).

Por supuesto, las diferencias se vuelven significativas solo si utiliza una operación de terminal diferente a la impresión de las coincidencias, ya que la impresión es una operación silenciosa y costosa. Del mismo modo, cuando la fuente es una secuencia sobre un archivo grande, la E / S dominará la operación. A menos que vaya en una dirección completamente diferente, como utilizar el mapeo de memoria y refactorizar esta operación para operar en ByteBuffer s.

1
Holger 10 sep. 2018 a las 10:19