viernes, 6 de septiembre de 2019

LISTAS RELACIONADAS CON LAS MATEMÁTICAS - ALGORITMOS


El algoritmo bitap (también conocido como el algoritmo shift-or , shift-and o Baeza-Yates – Gonnet ) es un algoritmo aproximado de coincidencia de cadenas. El algoritmo indica si un texto dado contiene una subcadena que es "aproximadamente igual" a un patrón dado, donde la igualdad aproximada se define en términos de distancia de Levenshtein  : si la subcadena y el patrón están dentro de una distancia dada k entre sí, entonces el algoritmo los considera iguales. El algoritmo comienza precomputando un conjunto de máscaras de bits que contienen un bit para cada elemento del patrón. Entonces es capaz de hacer la mayor parte del trabajo con operaciones bit a bit, que son extremadamente rápidos.
El algoritmo bitap es quizás mejor conocido como uno de los algoritmos subyacentes de la utilidad Unix agrep , escrito por Udi Manber , Sun Wu y Burra Gopal . El artículo original de Manber y Wu ofrece extensiones del algoritmo para tratar la coincidencia difusa de expresiones regulares generales .
Debido a las estructuras de datos requeridas por el algoritmo, funciona mejor en patrones de menos de una longitud constante (típicamente la longitud de la palabra de la máquina en cuestión), y también prefiere entradas sobre un alfabeto pequeño. Sin embargo, una vez que se ha implementado para un alfabeto dado y una longitud de palabra m , su tiempo de ejecución es completamente predecible: se ejecuta en operaciones O ( mn ), sin importar la estructura del texto o el patrón.
El algoritmo bitap para la búsqueda exacta de cadenas fue inventado por Bálint Dömölki en 1964 [1] [2] y extendido por RK Shyamasundar en 1977 [3] , antes de ser reinventado en el contexto de la búsqueda de cadenas difusas por Manber y Wu en 1991 [4] [5] basado en el trabajo realizado por Ricardo Baeza-Yates y Gaston Gonnet . [6] El algoritmo fue mejorado por Baeza-Yates y Navarro en 1996 [7] y más tarde por Gene Myers para patrones largos en 1998.

Búsqueda exacta [ editar ]

El algoritmo bitap para la búsqueda exacta de cadenas , en general, se ve así en pseudocódigo:
algoritmo bitap_search (texto: cadena, patrón: cadena) devuelve cadena
    m: = longitud (patrón)

    si m == 0
        texto de retorno

    / * Inicializa la matriz de bits R. * /
    R: = nueva matriz [m + 1] de bit, inicialmente todos 0
    R [0] = 1

    para i = 0; i i + = 1:
        / * Actualiza la matriz de bits. * /
        para k = m; k> = 1; k - = 1:
          R [k] = R [k-1] & (texto [i] == patrón [k-1])

        si R [m]:
             retorno (texto + i - m) + 1

    volver nulo
Bitap se distingue de otros algoritmos conocidos de búsqueda de cadenas en su mapeo natural en operaciones simples a nivel de bits, como en la siguiente modificación del programa anterior. Observe que en esta implementación, contraintuitivamente, cada bit con valor cero indica una coincidencia, y cada bit con valor 1 indica una no coincidencia. El mismo algoritmo se puede escribir con la semántica intuitiva para 0 y 1, pero en ese caso debemos introducir otra instrucción en el bucle interno para establecer R |= 1. En esta implementación, aprovechamos el hecho de que desplazar a la izquierda un valor se desplaza en ceros a la derecha, que es precisamente el comportamiento que necesitamos.
Observe también que requerimos CHAR_MAXmáscaras de bits adicionales para convertir la (text[i] == pattern[k-1])condición en la implementación general en operaciones bit a bit. Por lo tanto, el algoritmo bitap funciona mejor cuando se aplica a entradas sobre alfabetos más pequeños.
 #include  
 #include  
 
 const  char  * bitap_bitwise_search ( const  char  * text ,  const  char  * pattern ) 
 { 
     int  m  =  strlen ( pattern ); 
     sin signo  largo  R ; 
     unsigned  long  pattern_mask [ CHAR_MAX + 1 ]; 
     int  i ;
 
     if  ( patrón [ 0 ]  ==  '\ 0' )  devuelve  texto ; 
     if  ( m  >  31 )  return  "¡El patrón es demasiado largo!" ;
  
     / * Inicializar la matriz de bits R * / 
     R  =  ~ 1 ;
 
     / * Inicializa las máscaras de bits del patrón * / 
     for  ( i = 0 ;  i  <=  CHAR_MAX ;  ++ i ) 
       pattern_mask [ i ]  =  ~ 0 ; 
     para  ( i = 0 ;  i  <  m ;  ++ i ) 
       patrón_mask [ patrón [ i ]]  & =  ~ ( 1UL  <<  i );
 
     for  ( i = 0 ;  text [ i ]  ! =  '\ 0' ;  ++ i )  { 
         / * Actualizar la matriz de bits * / 
         R  | =  pattern_mask [ text [ i ]]; 
         R  << =  1 ;
 
         if  ( 0  ==  ( R  &  ( 1UL  <<  m ))) 
           return  ( texto  +  i  -  m )  +  1 ; 
     }
 
     devuelve  NULL ; 
 }

Búsqueda difusa [ editar ]

Para realizar una búsqueda de cadena difusa utilizando el algoritmo bitap, es necesario extender la matriz de bits R a una segunda dimensión. En lugar de tener una sola matriz R que cambie a lo largo del texto, ahora tenemos k matrices distintas R 1 .. k . La matriz R i contiene una representación de los prefijos de patrón que coinciden con cualquier sufijo de la cadena actual con i o menos errores. En este contexto, un "error" puede ser una inserción, eliminación o sustitución; ver distancia de Levenshtein para más información sobre estas operaciones.
La implementación a continuación realiza una coincidencia difusa (devolviendo la primera coincidencia con hasta k errores) utilizando el algoritmo bitap difuso. Sin embargo, solo presta atención a las sustituciones, no a las inserciones o eliminaciones; en otras palabras, una distancia de Hamming de k . Como antes, la semántica de 0 y 1 se invierte de sus significados convencionales.








Un algoritmo fonética es un algoritmo de indexación de palabras con su pronunciación . La mayoría de los algoritmos fonéticos se desarrollaron para su uso con el idioma inglés [ cita requerida ] ; en consecuencia, la aplicación de las reglas a las palabras en otros idiomas podría no dar un resultado significativo.
Son necesariamente algoritmos complejos [de citas necesarias ] con muchas reglas y excepciones, porque la ortografía y la pronunciación en inglés se complican por los cambios históricos en la pronunciación y las palabras prestadas de muchos idiomas .

Algoritmos [ editar ]

Entre los algoritmos fonéticos más conocidos se encuentran:
  • Soundex , que fue desarrollado para codificar apellidos para su uso en censos. Los códigos Soundex son cadenas de cuatro caracteres compuestas de una sola letra seguida de tres números.
  • Daitch – Mokotoff Soundex , que es un refinamiento de Soundex diseñado para combinar mejor los apellidos de origen eslavo y germánico. Los códigos Daitch – Mokotoff Soundex son cadenas compuestas de seis dígitos numéricos.
  • Fonética de Colonia : es similar a Soundex, pero más adecuada para palabras alemanas.
  • Metaphone , Double Metaphone y Metaphone 3 que son adecuados para usar con la mayoría de las palabras en inglés, no solo con los nombres. Los algoritmos de metafonía son la base de muchos correctores ortográficos populares .
  • Sistema de Identificación e Inteligencia del Estado de Nueva York (NYSIIS), que mapea fonemas similares a la misma letra. El resultado es una cadena que el lector puede pronunciar sin decodificar.
  • Enfoque de clasificación de partidos desarrollado por Western Airlines en 1977: este algoritmo tiene una técnica de codificación y comparación de rango.
  • Caverphone , creado para ayudar en la coincidencia de datos entre las listas electorales de finales del siglo XIX y principios del siglo XX, optimizado para los acentos presentes en partes de Nueva Zelanda.

Usos comunes [ editar ]

  • Los correctores ortográficos a menudo pueden contener algoritmos fonéticos. El algoritmo Metaphone , por ejemplo, puede tomar una palabra mal escrita y crear un código. Luego se busca el código en el directorio para buscar palabras con el mismo o similar Metaphone. Las palabras que tienen el mismo o similar Metaphone se convierten en posibles deletreos alternativos.
  • La funcionalidad de búsqueda a menudo utilizará algoritmos fonéticos para encontrar resultados que no coincidan exactamente con los términos utilizados en la búsqueda. La búsqueda de nombres puede ser difícil, ya que a menudo hay múltiples ortografías alternativas para los nombres. Un ejemplo es el nombre Claire . Tiene dos alternativas, Clare / Clair, que se pronuncian igual. Buscar una ortografía no mostraría resultados para las otras dos. Al usar Soundex, las tres variaciones producen el mismo código Soundex, C460. Al buscar nombres basados ​​en el código Soundex, se devolverán las tres variaciones.











Daitch – Mokotoff Soundex (D – M Soundex) es un algoritmo fonético inventado en 1985 por los genealogistas judíos Gary Mokotoff y Randy Daitch . Es un refinamiento de los algoritmos Soundex de Russell y American diseñados para permitir una mayor precisión en la coincidencia de apellidos eslavos y yiddish con pronunciación similar pero diferencias en la ortografía.
Daitch – Mokotoff Soundex a veces se conoce como "Jewish Soundex" y "Eastern European Soundex", aunque los autores desaconsejan el uso de estos apodos para el algoritmo porque el algoritmo en sí mismo es independiente del hecho de que la motivación para crear el nuevo sistema era la pobreza. resultados de sistemas predecesores cuando se trata de apellidos eslavos y yiddish.

Mejoras [ editar ]

Las mejoras sobre los algoritmos Soundex más antiguos incluyen:
  • Los nombres codificados tienen seis dígitos, lo que resulta en una mayor precisión de búsqueda (Soundex tradicional usa cuatro caracteres)
  • El carácter inicial del nombre está codificado.
  • Varias reglas en el algoritmo codifican n-gramas de caracteres múltiples como dígitos únicos (American y Russell Soundex no manejan n-gramas de caracteres múltiples)
  • Se pueden devolver múltiples codificaciones posibles para un solo nombre (Soundex tradicional solo devuelve una codificación, incluso si la ortografía de un nombre podría tener múltiples pronunciaciones)

Ejemplos [ editar ]

Algunos ejemplos:
ApellidoAmerican SoundexD – M Soundex
PetersP362739400, 734000
PetersonP362739460, 734600
MoskowitzM232645740
MoskovitzM213645740
AuerbachA612097500, 097400
UhrbachU612097500, 097400
JacksonJ250154600, 454600, 145460, 445460
Jackson-JacksonJ252154664, 454664, 145466, 445466, 154646, 454646, 145464, 445464

Algoritmo de coincidencia de nombres fonéticos de Beider-Morse [ editar ]

Para abordar la gran cantidad de resultados falsos positivos generados por D-M Soundex, Stephen P. Morse y Alexander Beider crearon el algoritmo de coincidencia de nombres fonéticos Beider-Morse. [1] Este nuevo algoritmo reduce los falsos positivos a expensas de algunos falsos negativos. Varios sitios ofrecen el índice de sonido B – M además del índice de sonido DM. 









Metaphone es un algoritmo fonético , publicado por Lawrence Philips en 1990, para indexar palabras por su pronunciación en inglés. [1] Mejora fundamentalmente el algoritmo Soundex mediante el uso de información sobre variaciones e inconsistencias en la ortografía y pronunciación en inglés para producir una codificación más precisa, lo que hace un mejor trabajo de emparejar palabras y nombres que suenan similares. Al igual que con Soundex, las palabras de sonido similar deberían compartir las mismas claves. Metaphone está disponible como operador integrado en varios sistemas.
El autor original más tarde produjo una nueva versión del algoritmo, al que llamó Double Metaphone . Contrariamente al algoritmo original cuya aplicación se limita al inglés solamente, esta versión tiene en cuenta las peculiaridades ortográficas de varios otros idiomas. En 2009, Lawrence Philips lanzó una tercera versión, llamada Metaphone 3, que logra una precisión de aproximadamente el 99% para las palabras en inglés, palabras que no están en inglés familiares para los estadounidenses, y los nombres y apellidos que se encuentran comúnmente en los Estados Unidos, que se han desarrollado de acuerdo con según los estándares de ingeniería modernos contra un arnés de prueba de codificaciones correctas preparadas.

Procedimiento [ editar ]

Los códigos originales de Metaphone usan los 16 símbolos de consonantes 0BFHJKLMNPRSTWXY. El '0' representa " th " (como una aproximación ASCII de Θ ), 'X' representa " sh " o " ch ", y los otros representan sus pronunciaciones habituales en inglés. Las vocales AEIOU también se usan, pero solo al comienzo del código. [2] Esta tabla resume la mayoría de las reglas en la implementación original:
  1. Suelte letras adyacentes duplicadas, excepto C.
  2. Si la palabra comienza con 'KN', 'GN', 'PN', 'AE', 'WR', suelte la primera letra.
  3. Suelta 'B' si después de 'M' al final de la palabra.
  4. 'C' se transforma en 'X' si es seguido por 'IA' o 'H' (a menos que en este último caso, sea parte de '-SCH-', en cuyo caso se transforma en 'K'). 'C' se transforma en 'S' si es seguido por 'I', 'E' o 'Y'. De lo contrario, 'C' se transforma en 'K'.
  5. 'D' se transforma en 'J' si es seguido por 'GE', 'GY' o 'GI'. De lo contrario, 'D' se transforma en 'T'.
  6. Suelta 'G' si es seguido por 'H' y 'H' no está al final o antes de una vocal. Suelta 'G' si seguido de 'N' o 'NED' y está al final.
  7. 'G' se transforma en 'J' si antes de 'I', 'E' o 'Y', y no está en 'GG'. De lo contrario, 'G' se transforma en 'K'.
  8. Suelte 'H' si después de la vocal y no antes de una vocal.
  9. 'CK' se transforma en 'K'.
  10. 'PH' se transforma en 'F'.
  11. 'Q' se transforma en 'K'.
  12. 'S' se transforma en 'X' si es seguido por 'H', 'IO' o 'IA'.
  13. 'T' se transforma en 'X' si es seguido por 'IA' o 'IO'. 'TH' se transforma en '0'. Suelta 'T' si seguido de 'CH'.
  14. 'V' se transforma en 'F'.
  15. 'WH' se transforma en 'W' si al principio. Suelta 'W' si no es seguido de una vocal.
  16. 'X' se transforma en 'S' si al principio. De lo contrario, 'X' se transforma en 'KS'.
  17. Suelta 'Y' si no es seguido de una vocal.
  18. 'Z' se transforma en 'S'.
  19. Suelta todas las vocales a menos que sea el comienzo.
Esta tabla no constituye una descripción completa del algoritmo original de Metaphone, y el algoritmo no puede codificarse correctamente a partir de él. Metaphone original contenía muchos errores y fue reemplazado por Double Metaphone, y a su vez, Double Metaphone y Metaphone original fueron reemplazados por Metaphone 3, que corrige miles de errores que se producirán en las dos primeras versiones.
Para implementar Metaphone sin comprar una copia (código fuente) de Metaphone 3, se puede usar la implementación de referencia de Double Metaphone. [3]

Doble metaphone [ editar ]

El algoritmo de codificación fonética Double Metaphone es la segunda generación de este algoritmo. Su implementación se describió en la edición de junio de 2000 de C / C ++ Users Journal . Hace una serie de mejoras de diseño fundamentales sobre el algoritmo original de Metaphone.
Se llama "Doble" porque puede devolver un código primario y uno secundario para una cadena; esto explica algunos casos ambiguos, así como múltiples variantes de apellidos con ascendencia común. Por ejemplo, codificar el nombre "Smith" produce un código primario de SM0 y un código secundario de XMT , mientras que el nombre "Schmidt" produce un código primario de XMT y un código secundario de SMT, ambos tienen XMT en común.
Double Metaphone intenta explicar innumerables irregularidades en inglés de origen eslavo , germánico , celta , griego , francés , italiano , español , chino y otros. Por lo tanto, utiliza un conjunto de reglas mucho más complejo para la codificación que su predecesor; por ejemplo, prueba aproximadamente 100 contextos diferentes del uso de la letra C solo.

Metaphone 3 [ editar ]

Una versión profesional fue lanzada en octubre de 2009, desarrollada por el mismo autor, Lawrence Philips. Es un producto comercial vendido como código fuente. Metaphone 3 mejora aún más la codificación fonética de palabras en el idioma inglés, palabras que no están en inglés familiares para los estadounidenses y los nombres y apellidos que se encuentran comúnmente en los Estados Unidos. Mejora la codificación de nombres propios en particular en gran medida. [4]El autor afirma que, en general, mejora la precisión de todas las palabras, desde aproximadamente el 89% de Double Metaphone hasta el 98%. Los desarrolladores ahora también pueden configurar interruptores en el código para hacer que el algoritmo codifique las teclas del Metaphone 1) teniendo en cuenta las vocales no iniciales, así como 2) codificando las consonantes sonoras y sordas de manera diferente. Esto permite que el conjunto de resultados esté más enfocado si el desarrollador encuentra que los resultados de búsqueda incluyen demasiadas palabras que no se parecen lo suficiente al término de búsqueda. [5] Metaphone 3 se vende como fuente C ++, Java, C #, PHP, Perl y PL / SQL, envoltorios Ruby y Python que acceden a un jar Java, y también Metaphone 3 para pronunciación en español y alemán disponible como fuente Java y C #. [6] La última revisión del algoritmo Metaphone 3 es v2.5.4, lanzada en marzo de 2015.

Conceptos erróneos comunes [ editar ]

Hay algunos conceptos erróneos sobre los algoritmos de Metaphone que deben abordarse. Las siguientes afirmaciones son verdaderas:
  1. Todos ellos están diseñados para abordar palabras regulares de "diccionario", no solo nombres, y
  2. Los algoritmos de metafonía no producen representaciones fonéticas de las palabras y nombres de entrada; más bien, la salida es una representación fonética intencionalmente aproximada , de acuerdo con este estándar:
  • las palabras que comienzan con un sonido de vocal tendrán una 'A', que representa cualquier vocal, como el primer carácter de la codificación (en Double Metaphone y Metaphone 3 - Metaphone original solo conserva la vocal real),
  • las vocales después de un sonido vocal inicial se ignorarán y no se codificarán, y
  • los pares de consonantes sonoras / sordas se asignarán a la misma codificación. (Ejemplos de pares de consonantes sonoras / sordas son D / T, B / P, Z / S, G / K, etc.).
Esta codificación aproximada es necesaria para tener en cuenta la forma en que los angloparlantes varían sus pronunciaciones y errores ortográficos o, de lo contrario, las palabras y los nombres que intentan deletrear. Las vocales, por supuesto, son notoriamente muy variables. Los hablantes británicos a menudo se quejan de que los estadounidenses parecen pronunciar 'T' es lo mismo que 'D'. Considere también que todos los hablantes de inglés a menudo pronuncian 'Z' donde se escribe 'S', casi siempre cuando un sustantivo que termina en una consonante sonora o un líquido está pluralizado, por ejemplo "estaciones", "haces", "ejemplos", etc. No codificar vocales después de un sonido vocal inicial ayudará a agrupar palabras donde una vocal y una consonante pueden transponerse en la ortografía o pronunciación alternativa.
Publicado por en

No hay comentarios:

Publicar un comentario

Suscribirse a: Enviar comentarios (Atom)