Me estoy enfrentando problemas en la comprensión de Boyer Moore Cadena algoritmo de Búsqueda.

Estoy siguiendo el siguiente documento. Enlace

No soy capaz de hacer funcionar mi camino exactamente lo que es el significado real de delta1 y delta2 aquí, y cómo están aplicando esto a la cadena de búsqueda del algoritmo de búsqueda.
Idioma pareció poco vago..

Amablemente si alguien aqui me puede ayudar en la comprensión de este, sería realmente útil.

O, si usted sabe de cualquier otro enlace o documento disponible que es fácil de entender, entonces, por favor compartir.

Gracias de antemano.

InformationsquelleAutor AGeek | 2011-06-01

2 Comentarios

  1. 46

    Primer consejo, tomar una respiración profunda. Está claro que eres estresado, y cuando usted está estresado, la primera cosa que sucede es que grandes porciones de su cerebro se apague. Esto hace que la comprensión de disco duro, lo que aumenta el estrés, y usted tiene un problema.

    A 5 minutos de tiempo de espera para mejorar su espacio de cabeza puede parecer imposible, pero puede ser sorprendentemente útil.

    Ahora que dijo, el algoritmo se basa en un principio simple. Supongamos que yo estoy tratando de coincidir con una subcadena de longitud m. Voy a mirar por primera vez el carácter en el índice m. Si el personaje no está en mi cadena, sé que la subcadena que quiero no se puede iniciar en los personajes en los índices de 1, 2, ... , m.

    Si el personaje está en mi cadena, voy a suponer que es en el último lugar en mi cadena que puede ser. Voy a luego volver y empezar a tratar a la altura de mi cadena desde la que sea posible lugar de partida. Esta pieza de información que es mi primera tabla.

    Una vez que se inicia coincidencia del inicio de la subcadena, cuando me encuentro una falta de coincidencia, yo simplemente no puede empezar de cero. Yo podría ser parcialmente a través de un partido de partida en un punto diferente. Por ejemplo, si estoy tratando de coincidir con anand en ananand coincidir con éxito, anan, darse cuenta de que el siguiente a no es un d, pero me he emparejado an, y por lo que debo volver a intentar para que coincida con mi tercer personaje en mi subcadena. Esto, «Si yo no después de la coincidencia de x caracteres, que podría ser en el y contando de un partido» la información es almacenada en la segunda tabla.

    Nota que cuando no coincide con la segunda tabla sabe cuánto tiempo, en un partido que podría estar basado en lo que acabo de igualada. La primera tabla sabe cómo yo podría estar basado en el personaje que acabo de ver que yo no se corresponden. Desea utilizar la más pesimista de las dos piezas de información.

    Con esto en mente que el algoritmo funciona de la siguiente manera:

    start at beginning of string
    start at beginning of match
    while not at the end of the string:
        if match_position is 0:
            Jump ahead m characters
            Look at character, jump back based on table 1
            If match the first character:
                advance match position
            advance string position
        else if I match:
            if I reached the end of the match:
               FOUND MATCH - return
            else:
               advance string position and match position.
        else:
            pos1 = table1[ character I failed to match ]
            pos2 = table2[ how far into the match I am ]
            if pos1 < pos2:
                jump back pos1 in string
                set match position at beginning
            else:
                set match position to pos2
    FAILED TO MATCH
    
    • Esto parecía un impresionante texto y explicación.. pero debido a que más de texto m lil’ confundido… estoy tratando de entender que ahora… de todas formas Gracias. Voy a dejar que usted knw cuando estoy hecho…
    • me pueden ayudar en la wiki programa de… la creación de la primera tabla… ¿qué es lo que realmente tratando de hacer…..
    • en.wikipedia.org/wiki/Boyer_moore >>> la primera creación de la tabla,,,, he leído el código también, pero cudn no tener la idea de cómo crear la primera tabla
    • Creo que se le preguntó acerca de la creación de tablas (salto de tablas), que no se muestra por su programa. Downvote para usted 🙁 es obvio que en caso de no coincidir el salto debe ser el máximo de tabla1 y tabla2. Pero la creación de las tablas es importante.
    • Pulgares para arriba para su consejo (Y).
  2. 113

    La idea detrás de Boyer-Moore es que si se inicia la búsqueda de un patrón en una cadena de inicio con el última carácter en el patrón, usted puede saltar en su búsqueda hacia adelante a varios personajes al llegar a un desajuste.

    Digamos que nuestro patrón de p es la secuencia de caracteres p1, p2, …, pn y estamos buscando una cadena s, actualmente con p alineados de modo que pn tiene el índice i en s.

    E. g.:

    s = WHICH FINALLY HALTS.  AT THAT POINT...
    p = AT THAT
    i =       ^
    

    El B-M de papel hace las siguientes observaciones:

    (1) si tratamos de coincidencia de un personaje que no está en p entonces podemos avanzar n caracteres:

    ‘F’ no es en p, por lo tanto hemos adelantado n caracteres:

    s = WHICH FINALLY HALTS.  AT THAT POINT...
    p =        AT THAT
    i =              ^
    

    (2) si tratamos de coincidencia de un personaje cuya última posición es k desde el final de p entonces podemos avanzar k caracteres:

    ‘ ‘s última posición en p es de 4 de la final, por lo tanto hemos adelantado 4 caracteres:

    s = WHICH FINALLY HALTS.  AT THAT POINT...
    p =            AT THAT
    i =                  ^
    

    Ahora podemos escanear hacia atrás desde i hasta que ya sea éxito o llegamos a un desajuste.
    (3a) si la discrepancia se produce k caracteres desde el inicio de p y los que no coinciden personaje no está en p, entonces podemos suficiente antelación (al menos) k caracteres.

    ‘L’ no es en p y el desajuste producido en contra de p6, de ahí que podamos suficiente antelación (al menos) 6 caracteres:

    s = WHICH FINALLY HALTS.  AT THAT POINT...
    p =                  AT THAT
    i =                        ^
    

    Sin embargo, en realidad podemos hacer mejor que esto.
    (3b), ya que sabemos que en el antiguo i ya habíamos emparejado algunos caracteres (1 en este caso). Si la coincidencia de caracteres no coinciden con el inicio de p, entonces realmente podemos avanzar un poco más (esta distancia adicional que se llama ‘delta2’ en el papel):

    s = WHICH FINALLY HALTS.  AT THAT POINT...
    p =                   AT THAT
    i =                         ^
    

    En este punto, la observación (2) se aplica de nuevo, dando

    s = WHICH FINALLY HALTS.  AT THAT POINT...
    p =                       AT THAT
    i =                             ^
    

    y ¡bingo! Hemos terminado.

    • Como queda claramente demostrado en esta respuesta, elaborar un ejemplo es, por lejos, la mejor y más sencilla manera de transmitir la esencia de cualquier sofisticado algoritmo.
    • leyenda. buen tutorial. en caso que alguien se está preguntando, horspool preprocesado de la tabla calcula salto = índice de desajuste, mientras que el BM preprocesado de la tabla calcula salto = más a la izquierda de índice de desajuste (por ejemplo, falta de coincidencia en S es ‘a’, por lo que saltan = izquierda más cercana ‘A’, de la mistmatch en el patrón). A veces, esto significa un mayor salto de horspool
    • Es increíble cómo muchas de «tutoriales» fallan en explicar una cosa tan simple con cientos de imágenes. Bien hecho @Rafe, que es la manera de explicar algo a la derecha.
    • muy amable de tu parte!
    • Todo bien con la explicación, PERO: todavía estoy confundido acerca de la primera de cambio. Todos los sitios mencionar que si tenemos un desajuste en la primera comparación, nos saltamos n caracteres de texto. Pero, ¿qué acerca de ejemplo: «aaaaabaakakakak» y el patrón «aaaab»? Si nos alineamos a la izquierda, b no es, pero si lo cambiamos por 5 caracteres a la derecha, nos flojo partido..
    • si tratamos de coincidencia de un personaje que no está en p
    • Ahh, por supuesto, mi mal:D gracias
    • Supongo que él se está preguntando cómo calcular el delta1 y delta2 tablas, la fórmula, por favor, ampliar la respuesta.

Dejar respuesta

Please enter your comment!
Please enter your name here