Algoritmo de coincidencia de cadenas paralelas de primer orden

Question

Para estar al frente, este es deberes. Dicho esto, es extremadamente abierto y casi no hemos tenido ninguna orientación sobre cómo empezar a pensar en este problema (o algoritmos paralelos en general). Me gustaría que los punteros en la dirección correcta y no es una solución completa. Cualquier lectura que pueda ayudar sería excelente también.

Estoy trabajando en una forma eficiente de hacer coincidir la primera aparición de un patrón en una gran cantidad de texto usando un algoritmo paralelo. El patrón es la coincidencia de caracteres simples, sin expresiones regulares involucradas. He logrado encontrar una forma posible de encontrar todas las de las coincidencias, pero eso requiere que mire todas las coincidencias y encuentre la primera.

Entonces, la pregunta es, ¿tendré más éxito al dividir el texto entre procesos y escanear de esa manera? ¿O sería mejor tener una búsqueda sincronizada en el proceso de algún tipo donde el proceso j'th busca el carácter j-ésimo del patrón? Si todos los procesos devuelven verdadero para su coincidencia, los procesos cambiarían su posición al hacer coincidir dicho patrón y subir de nuevo, continuar hasta que todos los caracteres se hayan emparejado y luego devolver el índice de la primera coincidencia.

Lo que tengo hasta ahora es extremadamente básico, y lo más probable es que no funcione. No implementaré esto, pero cualquier puntero sería apreciado.

Con los procesadores P, un texto de longitud T, y un patrón de longitud L, y un techo de procesadores L utilizado:

 
for i=0 to t-l: 
    for j=0 to p: 
     processor j compares the text[i+j] to pattern[i+j] 
      On false match: 
       all processors terminate current comparison, i++ 
      On true match by all processors: 
       Iterate p characters at a time until L characters have been compared 
       If all L comparisons return true: 
        return i (position of pattern) 
       Else: 
        i++ 

Answer 1

Me temo que romper el hilo no servirá.

Hablando en general, escaparse temprano es difícil, por lo que sería mejor romper el texto en pedazos.

Pero preguntemos a Herb Sutter para explicar la búsqueda con algoritmos paralelos primero en Dr Dobbs. La idea es usar la no uniformidad de la distribución para tener un retorno anticipado. Por supuesto, Sutter está interesado en cualquier coincidencia, que no es el problema en cuestión, así que vamos a adaptarnos.

Aquí es mi idea, supongamos que tenemos:

• texto de longitud N
• p Procesadores
• heurística: max es el número máximo de caracteres de un trozo debe contener, probablemente un orden de magnitud mayor que M la longitud del patrón.

Ahora, lo que quiere es dividir el texto en k trozos iguales, donde es k es mínima y máxima size(chunk) es todavía inferior a max.

Luego, tenemos un patrón clásico Producer-Consumer: los procesos p se alimentan con trozos de texto, cada proceso busca el patrón en el trozo que recibe.

El escape anticipado se realiza mediante una bandera. Puede establecer el índice del fragmento en el que encontró el patrón (y su posición), o simplemente puede establecer un booleano, y almacenar el resultado en los procesos en sí (en cuyo caso tendrá que pasar por todo el procesos una vez que se detienen). El punto es que cada vez que se solicita un trozo, el productor verifica el indicador y deja de alimentar los procesos si se ha encontrado una coincidencia (ya que a los procesos se les han dado los trozos en orden).

Tengamos un ejemplo, con 3 procesadores:

[ 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 ] 
         x  x 

Los trozos 6 y 8 ambos contienen la cadena.

El productor primero enviará 1, 2 y 3 a los procesos, luego cada proceso avanzará a su propio ritmo (depende de la similitud del texto buscado y el patrón).

Digamos que encontramos el patrón en 8 antes de encontrarlo en 6. Luego, el proceso que estaba trabajando en 7 finaliza e intenta obtener otro fragmento, el productor lo detiene -> sería irrelevante. Entonces el proceso que trabaja en 6 finaliza, con un resultado, y así sabemos que la primera aparición fue en 6, y tenemos su posición.

¡La idea clave es que no quiere ver el texto completo! ¡Es un desperdicio!

Answer 2

Dado un patrón de longitud L, y buscar en una cadena de longitud Procesadores N sobre P Simplemente dividiría la cadena sobre los procesadores. Cada procesador tomaría un trozo de longitud N/P + L-1, con el último L-1 superpuesto a la cadena perteneciente al siguiente procesador. Entonces, cada procesador realizaría boyer moore (las dos tablas de preprocesamiento se compartirían). Cuando cada uno de los acabados, van a devolver el resultado al primer procesador, el cual mantiene una tabla

Process Index 
    1 -1 
    2 2 
    3 23 

Después de todos los procesos han respondido (o con un poco de pensamiento que puede tener un escape antes de tiempo), que devuelve el primer partido . Esto debería ser en promedio O (N/(L * P) + P).

El enfoque de tener el procesador i que coincide con el carácter i-ésimo requeriría demasiada sobrecarga de comunicación entre procesos.

EDIT: Me doy cuenta de que ya tiene una solución, y está buscando una manera sin tener que encontrar todas las soluciones. Bueno, realmente no creo que este enfoque sea necesario. Puedes encontrar algunas condiciones de escape temprano, no son tan difíciles, pero no creo que mejoren tanto tu rendimiento en general (a menos que tengas algún conocimiento adicional sobre la distribución de las coincidencias en tu texto).