Encontrar un patrón en un conjunto
https://stackoverflow.com/questions/270541
-
06-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
¿Qué algoritmos podría usar para determinar caracteres comunes en un conjunto de cadenas?
Para simplificar el ejemplo, solo me interesan más de 2 caracteres seguidos y si aparece en 2 o más de la muestra. Por ejemplo:
- 0000abcde0000
- 0000abcd00000
- 000abc0000000
- 00abc000de000
Me gustaría saber:
00 se utilizó en 1,2,3,4
000 se utilizó en 1,2,3,4
0000 se utilizó en 1,2,3
00000 se utilizó en 2,3
ab se utilizó en 1,2,3,4
abc se usó en 1,2,3,4
abcd se utilizó en 1,2
bc se usó en 1,2,3,4
bcd se utilizó en 1,2
el cd se usó en 1,2
de fue utilizado en 1,4
Solución
Asumo que esto no es tarea. (Si es así, ¡eres uno tu propio re plagio! ;-)
A continuación hay una solución rápida y sucia. La complejidad temporal es O (m ** 2 * n) donde m es la longitud promedio de la cadena y n es el tamaño de la matriz de cadenas.
Una instancia de Ocurrencia mantiene el conjunto de índices que contienen una cadena dada. La rutina commonOccurrences escanea una matriz de cadenas, llamando a captureOccurrences para cada cadena no nula. La rutina captureOccurrences coloca el índice actual en un Ocurrencia para cada posible subcadena de la cadena que se le asigna. Finalmente, commonOccurrences forma el conjunto de resultados seleccionando solo aquellas Ocurrencias que tienen al menos dos índices.
Tenga en cuenta que sus datos de ejemplo tienen muchas más subcadenas comunes de las que identificó en la pregunta. Por ejemplo, " 00ab " aparece en cada una de las cadenas de entrada. Como dicen, un filtro adicional para seleccionar cadenas interesantes basadas en el contenido (por ejemplo, todos los dígitos, todos alfabéticos, etc.) se deja como ejercicio para el lector. ;-)
FUENTE DE JAVA RÁPIDA Y SUCIA:
package com.stackoverflow.answers;
import java.util.Collections;
import java.util.HashMap;
import java.util.Map;
import java.util.Set;
import java.util.TreeSet;
public class CommonSubstringFinder {
public static final int MINIMUM_SUBSTRING_LENGTH = 2;
public static class Occurrence implements Comparable<Occurrence> {
private final String value;
private final Set<Integer> indices;
public Occurrence(String value) {
this.value = value == null ? "" : value;
indices = new TreeSet<Integer>();
}
public String getValue() {
return value;
}
public Set<Integer> getIndices() {
return Collections.unmodifiableSet(indices);
}
public void occur(int index) {
indices.add(index);
}
public String toString() {
StringBuilder result = new StringBuilder();
result.append('"').append(value).append('"');
String separator = ": ";
for (Integer i : indices) {
result.append(separator).append(i);
separator = ",";
}
return result.toString();
}
public int compareTo(Occurrence that) {
return this.value.compareTo(that.value);
}
}
public static Set<Occurrence> commonOccurrences(String[] strings) {
Map<String,Occurrence> work = new HashMap<String,Occurrence>();
if (strings != null) {
int index = 0;
for (String string : strings) {
if (string != null) {
captureOccurrences(index, work, string);
}
++index;
}
}
Set<Occurrence> result = new TreeSet<Occurrence>();
for (Occurrence occurrence : work.values()) {
if (occurrence.indices.size() > 1) {
result.add(occurrence);
}
}
return result;
}
private static void captureOccurrences(int index, Map<String,Occurrence> work, String string) {
final int maxLength = string.length();
for (int i = 0; i < maxLength; ++i) {
for (int j = i + MINIMUM_SUBSTRING_LENGTH; j < maxLength; ++j) {
String partial = string.substring(i, j);
Occurrence current = work.get(partial);
if (current == null) {
current = new Occurrence(partial);
work.put(partial, current);
}
current.occur(index);
}
}
}
private static final String[] TEST_DATA = {
"0000abcde0000",
"0000abcd00000",
"000abc0000000",
"00abc000de000",
};
public static void main(String[] args) {
Set<Occurrence> found = commonOccurrences(TEST_DATA);
for (Occurrence occurrence : found) {
System.out.println(occurrence);
}
}
}
SALIDA DE MUESTRA: (tenga en cuenta que en realidad solo hubo una Ocurrencia por línea; parece que no puedo evitar que el marcado de blockquote combine líneas)
`` 00 '': 0,1,2,3 " 000 " ;: 0,1,2,3
" 0000 " ;: 0,1,2 " 0000a " ;: 0,1
" 0000ab " ;: 0,1 " 0000abc " ;: 0,1
" 0000abcd " ;: 0,1 " 000a " ;: 0,1,2
" 000ab " ;: 0,1,2 " 000abc " ;: 0,1,2
" 000abcd " ;: 0,1 " 00a " ;: 0,1,2,3
" 00ab " ;: 0,1,2,3 " 00abc " ;: 0,1,2,3
" 00abc0 " ;: 2,3 " 00abc00 " ;: 2,3
" 00abc000 " ;: 2,3 " 00abcd " ;: 0,1
" 0a " ;: 0,1,2,3 " 0ab " ;: 0,1,2,3
" 0abc " ;: 0,1,2,3 " 0abc0 " ;: 2,3
" 0abc00 " ;: 2,3 " 0abc000 " ;: 2,3
" 0abcd " ;: 0,1 " ab " ;: 0,1,2,3 " abc " ;: 0,1,2,3 " abc0 " ;: 2,3 " abc00 " ;: 2,3
" abc000 " ;: 2,3 " abcd " ;: 0,1 " bc " ;: 0,1,2,3 " bc0 " ;: 2,3 " bc00 " ;: 2,3
" bc000 " ;: 2,3 " bcd " ;: 0,1 " c0 " ;: 2,3 " c00 " ;: 2,3 " c000 " ;: 2,3 " cd " ;: 0,1
" de " ;: 0,3 " de0 " ;: 0,3 " de00 " ;: 0,3
" e0 " ;: 0,3 " e00 " ;: 0,3
Otros consejos
Este es probablemente un problema NP-difícil. Se parece a alineación de secuencia múltiple , que es. Básicamente, podría adaptar Smith-Waterman (= alineación de secuencia local) multidimensional para sus necesidades. . Sin embargo, puede haber un algoritmo más eficiente.
Construye un árbol donde el camino a través del árbol es la secuencia de letras. Haga que cada nodo contenga un " conjunto " que las referencias de cadena se agregan de pasada (o simplemente mantienen un recuento). Luego, realice un seguimiento de N ubicaciones en la palabra donde N es la secuencia más larga que le interesa (por ejemplo, comience un nuevo identificador en cada char caminando todos los identificadores en cada paso y anule cada identificador después de N pasos)
Esto funcionaría mejor con un alfabeto pequeño, finito y denso (el ADN fue el primer lugar donde pensé usarlo).
Editar: Si conoce de antemano el patrón que le interesa, lo anterior puede modificarse para que funcione construyendo el árbol con anticipación y luego solo verificando si está en el árbol. que extenderlo.
un ejemplo
entrada
abc
abd
abde
acc
bde
el árbol
a : 4
b : 3
c : 1
d : 2
e : 1
c : 1
c : 1
b : 4
d : 3
e : 2
c : 1
c : 3
c : 1
d : 3
e : 2
Buscar "Árboles de sufijo" En la red. O recoge "Algoritmos de cadenas, árboles y secuencias". por Dan Gusfield. No tengo el libro conmigo para verificar, pero la página de wikipedia en árboles de sufijos dice esa página 205 contiene una solución para su problema: "encontrar las subcadenas más largas comunes al menos a k cadenas en un conjunto".
¿Conoces los " valores " necesitas buscar antes de tiempo? ¿O necesita un código para analizar las cadenas y darle estadísticas como las que publicó?
El uso del algoritmo Boyer-Moore es una forma muy rápida de saber si existen subcadenas (e incluso ubicarlas), si sabe lo que está buscando con anticipación.
puede usar un análisis de matriz de distancia. Cualquier movimiento diagonal (sin cambio de costo) es una coincidencia exacta.
Puede encontrar una matriz de sufijos más simple y más eficiente que un árbol de sufijos, dependiendo de qué tan frecuentes son las subcadenas comunes en sus datos; si son lo suficientemente comunes, necesitará el algoritmo de construcción de matriz de sufijo más sofisticado. (El método ingenuo es usar la función de clasificación de su biblioteca).
