java - programacion - Manera eficiente de buscar una secuencia por una cadena

manual de programacion android pdf

Question

Supongamos que tenemos una secuencia de texto (o Reader en Java) que quisiera verificar para una cadena en particular. La secuencia de texto puede ser muy grande, así que tan pronto como se encuentre la cadena de búsqueda, me gustaría volver verdadero y también tratar de evitar almacenar toda la entrada en la memoria.

Ingenuamente, podría intentar hacer algo como esto (en Java):

public boolean streamContainsString(Reader reader, String searchString) throws IOException {
    char[] buffer = new char[1024];
    int numCharsRead;
    while((numCharsRead = reader.read(buffer)) > 0) {
        if ((new String(buffer, 0, numCharsRead)).indexOf(searchString) >= 0)
            return true;
    }
    return false;
}

Por supuesto, esto no detecta la cadena de búsqueda dada si ocurre en el límite del buffer 1k:

Texto de búsqueda: "stackoverflow"
Almacenamiento intermedio 1: "abc ......... stack"
Almacenamiento intermedio 2: "desbordamiento ....... xyz"

¿Cómo puedo modificar este código para que encuentre correctamente la cadena de búsqueda dada a través del límite del búfer pero sin cargar todo el flujo en la memoria?

Editar: Tenga en cuenta que cuando buscamos una secuencia para una secuencia, intentamos minimizar el número de lecturas de la secuencia (para evitar la latencia en una red / disco) y mantener el uso de la memoria constante independientemente de la cantidad de datos en la secuencia. La eficacia real del algoritmo de coincidencia de cadenas es secundaria, pero obviamente, sería bueno encontrar una solución que utilizara uno de los algoritmos más eficientes.

Answer 1

Aquí hay tres buenas soluciones:

1. Si desea algo que sea fácil y razonablemente rápido, vaya sin memoria intermedia e implemente una máquina de estado finito no determinística simple. Su estado será una lista de índices en la cadena que está buscando, y su lógica se ve más o menos así (pseudocódigo):

   String needle;
   n = needle.length();
   
   for every input character c do
     add index 0 to the list
     for every index i in the list do
       if c == needle[i] then
         if i + 1 == n then
           return true
         else
           replace i in the list with i + 1
         end
       else
         remove i from the list
       end
     end
   end

   Esto encontrará la cadena si existe y nunca necesitarás un buffer.

2. Un poco más de trabajo pero también más rápido: haga una conversión de NFA a DFA que descubra de antemano qué listas de índices son posibles y asigne cada uno a un número entero pequeño. (Si lees sobre la búsqueda de cadenas en Wikipedia, esto se llama construcción powerset ). Entonces tienes un único estado y realizas una transición de estado a estado en cada carácter entrante. El NFA que desea es solo el DFA para la cadena precedida por un estado que, de forma no determinista, suelta un carácter o intenta consumir el carácter actual. También querrás un estado de error explícito.

3. Si quieres algo más rápido, crea un buffer cuyo tamaño es al menos dos veces n , y el usuario Boyer-Moore para compilar una máquina de estado de la needle . Tendrá muchos problemas adicionales porque Boyer-Moore no es trivial de implementar (aunque encontrará el código en línea) y porque deberá organizar deslizar la cuerda a través del búfer. Tendrás que crear o encontrar un búfer circular que pueda ''deslizarse'' sin copiar; de lo contrario, es probable que devuelva los aumentos de rendimiento que pueda obtener de Boyer-Moore.

Answer 2

Creo que debes almacenar una pequeña cantidad en el límite entre los buffers.

Por ejemplo, si su tamaño de búfer es 1024 y la longitud de SearchString es 10, entonces además de buscar cada búfer de 1024 bytes, también debe buscar cada transición de 18 bytes entre dos búferes (9 bytes desde el final del búfer anterior concatenado con 9 bytes desde el inicio del siguiente buffer).

Answer 3

Creo que la mejor solución a este problema es tratar de mantenerlo simple. Recuerde, porque estoy leyendo de una transmisión, quiero mantener el número de lecturas de la transmisión al mínimo (ya que la latencia de la red o del disco puede ser un problema) mientras se mantiene constante la cantidad de memoria utilizada (ya que la transmisión puede ser muy grande en tamaño). La eficacia real de la coincidencia de cadenas no es el objetivo número uno (ya que se ha estudiado hasta la muerte ).

En base a la sugerencia de AlbertoPL, aquí hay una solución simple que compara el buffer con la cadena de búsqueda carácter por carácter. La clave es que debido a que la búsqueda solo se realiza de a un carácter a la vez, no se necesita un seguimiento posterior y, por lo tanto, no se necesitan almacenamientos intermedios circulares o almacenamientos intermedios de un tamaño particular.

Ahora, si alguien puede llegar a una implementación similar basada en el algoritmo de búsqueda de Knuth-Morris-Pratt, entonces tendríamos una buena solución eficiente;)

public boolean streamContainsString(Reader reader, String searchString) throws IOException {
    char[] buffer = new char[1024];
    int numCharsRead;
    int count = 0;
    while((numCharsRead = reader.read(buffer)) > 0) {
        for (int c = 0; c < numCharsRead; c++) {
            if (buffer[c] == searchString.charAt(count))
                count++;
            else
                count = 0;
            if (count == searchString.length()) return true;
        }
    }
    return false;
}

Answer 4

El algoritmo de búsqueda Knuth-Morris-Pratt nunca hace copias de seguridad; esta es solo la propiedad que desea para su búsqueda en tiempo real. Lo he usado antes para este problema, aunque puede haber maneras más fáciles usando las bibliotecas Java disponibles. (Cuando esto surgió, estaba trabajando en C en los 90).

En esencia, KMP es una forma rápida de crear un DFA de coincidencia de cuerdas, como la sugerencia N. ° 2 de Norman Ramsey.

Answer 5

En lugar de hacer que su buffer sea una matriz, use una abstracción que implemente un buffer circular . El cálculo de su índice será buf[(next+i) % sizeof(buf)] , y deberá tener cuidado de llenar el buffer por la mitad cada vez. Pero mientras la cadena de búsqueda encaje en la mitad del búfer, la encontrará.

Answer 6

Es posible que pueda implementar una solución muy rápida utilizando Fast Fourier Transforms, que, si se implementa correctamente, le permite hacer coincidencias de cadenas en tiempos O (nlog (m)), donde n es la longitud de la cadena más larga con la que se emparejarán, y m es la longitud de la cadena más corta. Podría, por ejemplo, realizar FFT tan pronto como reciba una entrada de flujo de longitud m, y si coincide, puede regresar, y si no coincide, puede descartar el primer carácter en la entrada de flujo, esperar para que aparezca un nuevo personaje a través de la secuencia, y luego realice FFT nuevamente.

Answer 7

Esta respuesta se aplicaba a la versión inicial de la pregunta donde la clave era leer la transmisión solo en la medida necesaria para coincidir en una Cadena, si esa Cadena estaba presente. Esta solución no cumpliría el requisito de garantizar la utilización de la memoria fija, pero puede valer la pena considerarla si ha encontrado esta pregunta y no está sujeto a esa restricción.

Si está sujeto a la restricción de uso de memoria constante, Java almacena matrices de cualquier tipo en el montón, y como tal, anular la referencia no desasigna memoria de ninguna manera; Creo que cualquier solución que involucre matrices en un bucle consumirá memoria en el montón y requerirá GC.

Para una implementación simple, tal vez el Scanner Java 5 que puede aceptar un InputStream y usar un java.util.regex.Pattern para buscar la entrada puede ahorrarle preocuparse por los detalles de la implementación.

Aquí hay un ejemplo de una posible implementación:

public boolean streamContainsString(Reader reader, String searchString)
            throws IOException {
      Scanner streamScanner = new Scanner(reader);
      if (streamScanner.findWithinHorizon(searchString, 0) != null) {
        return true;
      } else {
        return false;
      }
}

Estoy pensando en expresiones regulares porque suena como un trabajo para un autómata de estados finitos, algo que comienza en un estado inicial, cambiando el carácter por carácter hasta que rechaza la cadena (no coincide) o llega a un estado de aceptación.

Creo que esta es probablemente la lógica de comparación más eficiente que podría usar, y la forma en que organiza la lectura de la información puede separarse de la lógica de coincidencia para la optimización del rendimiento.

También es cómo funcionan las expresiones regulares.

Answer 8

Hice algunos cambios al algoritmo de Knuth Morris Pratt para búsquedas parciales. Como la posición de comparación real es siempre menor o igual que la siguiente, no hay necesidad de memoria adicional. El código con un Makefile también está disponible en github y está escrito en Haxe para apuntar a múltiples lenguajes de programación a la vez, incluido Java.

También escribí un artículo relacionado: búsqueda de subcadenas en transmisiones: una ligera modificación del algoritmo Knuth-Morris-Pratt en Haxe . El artículo menciona el Yakarta RegExp , ahora retirado y descansando en el ático Apache. El método de " match " de la biblioteca Jakarta Regexp en la clase RE utiliza un CharacterIterator como parámetro.

class StreamOrientedKnuthMorrisPratt {
    var m: Int;
    var i: Int;
    var ss:
    var table: Array<Int>;

    public function new(ss: String) {
        this.ss = ss;
        this.buildTable(this.ss);
    }

    public function begin() : Void {
        this.m = 0;
        this.i = 0;
    }

    public function partialSearch(s: String) : Int {
        var offset = this.m + this.i;

        while(this.m + this.i - offset < s.length) {
            if(this.ss.substr(this.i, 1) == s.substr(this.m + this.i - offset,1)) {
                if(this.i == this.ss.length - 1) {
                    return this.m;
                }
                this.i += 1;
            } else {
                this.m += this.i - this.table[this.i];
                if(this.table[this.i] > -1)
                    this.i = this.table[this.i];
                else
                    this.i = 0;
            }
        }

        return -1;
    }

    private function buildTable(ss: String) : Void {
        var pos = 2;
        var cnd = 0;

        this.table = new Array<Int>();
        if(ss.length > 2)
            this.table.insert(ss.length, 0);
        else
            this.table.insert(2, 0);

        this.table[0] = -1;
        this.table[1] = 0;

        while(pos < ss.length) {
            if(ss.substr(pos-1,1) == ss.substr(cnd, 1))
            {
                cnd += 1;
                this.table[pos] = cnd;
                pos += 1;
            } else if(cnd > 0) {
                cnd = this.table[cnd];
            } else {
                this.table[pos] = 0;
                pos += 1;
            }
        }
    }

    public static function main() {
        var KMP = new StreamOrientedKnuthMorrisPratt("aa");
        KMP.begin();
        trace(KMP.partialSearch("ccaabb"));

        KMP.begin();
        trace(KMP.partialSearch("ccarbb"));
        trace(KMP.partialSearch("fgaabb"));

    }
}

Answer 9

Implementar una ventana deslizante. Tenga su búfer, mueva todos los elementos en el búfer uno hacia adelante e ingrese un único carácter nuevo en el búfer al final. Si el buffer es igual a su palabra buscada, está contenido.

Por supuesto, si desea hacer esto más eficiente, puede buscar una forma de evitar mover todos los elementos en el búfer, por ejemplo, teniendo un búfer cíclico y una representación de las cadenas que "cicla" de la misma manera que el búfer lo hace, por lo que solo debe verificar la igualdad de contenido. Esto ahorra mover todos los elementos en el búfer.

Answer 10

Puede aumentar la velocidad de búsqueda de cadenas muy grandes utilizando algún algoritmo de búsqueda de cadenas

Answer 11

Se implementa una búsqueda muy rápida de una secuencia en la clase RingBuffer desde el framework Ujorm. Ver la muestra:

 Reader reader = RingBuffer.createReader("xxx ${abc} ${def} zzz");

 String word1 = RingBuffer.findWord(reader, "${", "}");
 assertEquals("abc", word1);

 String word2 = RingBuffer.findWord(reader, "${", "}");
 assertEquals("def", word2);

 String word3 = RingBuffer.findWord(reader, "${", "}");
 assertEquals("", word3);

La implementación de clase única está disponible en SourceForge : para obtener más información, consulte el link .

Answer 12

Si buscas una subcadena constante en lugar de una expresión regular, te recomendaría Boyer-Moore. Hay un montón de código fuente en internet.

Además, use un buffer circular, para evitar pensar demasiado sobre los límites del buffer.

Micro.

Answer 13

Si no está vinculado al uso de un lector, puede usar la API NIO de Java para cargar el archivo de manera eficiente. Por ejemplo (no probado, pero debe estar cerca de funcionar):

public boolean streamContainsString(File input, String searchString) throws IOException {
    Pattern pattern = Pattern.compile(Pattern.quote(searchString));

    FileInputStream fis = new FileInputStream(input);
    FileChannel fc = fis.getChannel();

    int sz = (int) fc.size();
    MappedByteBuffer bb = fc.map(FileChannel.MapMode.READ_ONLY, 0, sz);

    CharsetDecoder decoder = Charset.forName("UTF-8").newDecoder();
    CharBuffer cb = decoder.decode(bb);

    Matcher matcher = pattern.matcher(cb);

    return matcher.matches();
}

Básicamente, mmap () es el archivo para buscar y depende del sistema operativo para hacer lo correcto con respecto al uso de la memoria caché y la memoria. Sin embargo, tenga en cuenta que map () es más caro que leer el archivo en un búfer grande para archivos de menos de 10 KiB.

Answer 14

También tuve un problema similar: omitir bytes desde el InputStream hasta la cadena especificada (o matriz de bytes). Este es el código simple basado en el buffer circular. No es muy eficiente pero funciona para mis necesidades:

  private static boolean matches(int[] buffer, int offset, byte[] search) {
    final int len = buffer.length;
    for (int i = 0; i < len; ++i) {
      if (search[i] != buffer[(offset + i) % len]) {
        return false;
      }
    }
    return true;
  }

  public static void skipBytes(InputStream stream, byte[] search) throws IOException {
    final int[] buffer = new int[search.length];
    for (int i = 0; i < search.length; ++i) {
      buffer[i] = stream.read();
    }

    int offset = 0;
    while (true) {
      if (matches(buffer, offset, search)) {
        break;
      }
      buffer[offset] = stream.read();
      offset = (offset + 1) % buffer.length;
    }
  }

Answer 15

Yo diría que cambien a una solución de personaje por personaje, en cuyo caso buscarán el primer personaje en su texto objetivo, y luego, cuando encuentren ese personaje, aumentarán el contador y buscarán el siguiente personaje. Cada vez que no encuentre el siguiente personaje consecutivo, reinicie el contador. Funcionaría así:

public boolean streamContainsString(Reader reader, String searchString) throws IOException {
char[] buffer = new char[1024];
int numCharsRead;
int count = 0;
while((numCharsRead = reader.read(buffer)) > 0) {
    if (buffer[numCharsRead -1] == searchString.charAt(count))
        count++;
    else
        count = 0;

    if (count == searchString.size())    
     return true;
}
return false; 
}

El único problema es cuando estás en el medio de mirar a través de los personajes ... en cuyo caso debe haber una forma de recordar tu variable de conteo. No veo una manera fácil de hacerlo, excepto como una variable privada para toda la clase. En cuyo caso, usted no instanciaría la cuenta dentro de este método.