Algoritmo de coincidencia de cadenas ingenuas en Python: ejemplos, destacados y pros y contras

Cuando existe la necesidad de encontrar un patrón de entrada en una cadena de caracteres, los codificadores y programadores utilizan el algoritmo de coincidencia de cadenas. Por lo general, en el caso de una cadena corta, los programadores de Python prefieren usar el enfoque ingenuo en el que el programa verifica cada posición en la cadena de entrada para el patrón de consulta. En caso de que coincida, da una salida con el número de posición.

Una de las principales razones por las que se utiliza el algoritmo de coincidencia de cadenas ingenuo es porque es rápido y produce resultados bastante precisos. Además, no requiere procesamiento previo. En cualquier caso, discutiremos estas ventajas en una etapa posterior de esta publicación. Primero comprendamos el algoritmo para la búsqueda de patrones utilizando el enfoque ingenuo.

Algoritmo de búsqueda de patrón ingenuo

En la búsqueda ingenua de patrón de cadena, el programa prueba la posición del patrón de entrada P [1……i] en una cadena de caracteres T [1…..m].

Tenga en cuenta que la longitud del texto o cadena de entrada siempre será mayor o igual que la del patrón.

Aquí está el algoritmo de búsqueda de patrones ingenuo para diferentes lenguajes de programación.

Empezar

pat = tamaño del patrón

str = tamaño de la cadena

para i = 0 a (str – pat), hacer

para j = 0 para pat, hacer

si texto[i+j] ≠ patrón[j], entonces

romper el bucle

hecho

si j == pat, entonces

mostrar la posición de i como patrón encontrado

hecho

Final

Este algoritmo es bastante importante en informática, ya que ayuda a dar resultados de búsqueda como salida.

Leer: Tipos de algoritmos de IA que debe conocer

Ejemplos de coincidencia de cadenas ingenuas en Python

Aquí hay un ejemplo en el que se usa el enfoque de búsqueda de patrones ingenuos en un código de python.

# Programa de Python para coincidencia de cadenas ingenuas

# Algoritmo de búsqueda

búsqueda de definición (P, T):

X = largo(P)

Y = largo(T)

# Un ciclo para cambiar P[] uno por uno */

para i en el rango (X – Y + 1):

j = 0

# Para el índice actual i, marque

# para coincidencia de patrón */

para j en el rango (0, X):

si (txt[i + j] ! = P[j]):

descanso

si (j == X – 1):

imprimir ("Patrón encontrado en la posición", i)

# código de conductor

si __nombre__ == '__principal__':

T = “ACTUALIZADOUBUPGRAABUPGRADEDU”

P = "ACTUALIZAR"

buscar (P, T)

Salida :

Patrón encontrado en la posición 0

Patrón encontrado en la posición 17

Explicación: La primera posición es la posición 0 . Dado que el patrón "UPGRAD" se detectó por primera vez aquí, el resultado mostró que el patrón se encuentra en la posición 0.

De manera similar, el siguiente patrón se encontró en la posición 17.

Mejor caso de búsqueda de patrones ingenuos

Solo hay un mejor caso para el algoritmo de búsqueda de patrones ingenuos, a diferencia de los dos peores casos.

El mejor caso ocurre cuando el primer carácter en el texto del patrón no está en ninguna parte de la cadena de entrada.

Ejemplo:

T [] = “UPGRADEDUHIJKLUPGRA”;

P[] = “TUGRA”;

Y por lo tanto, el número de casos de patrones coincidentes es O(n).

Peor caso de búsqueda de patrones ingenuos

Hay dos peores casos en el enfoque de búsqueda de cadenas ingenuas.

1. Cuando todos los caracteres del patrón son los mismos que los de la cadena de entrada.

T [] = “EEEEEEEEEEEEEEEE”;

P [] = “EEE”;

1. Cuando solo el último carácter del patrón difiere de la cadena de entrada.

T [] = “EEEEEEEEEEED”;

P [] = “EEEED”;

En tales casos, el número de comparaciones en O(m*(n-m+1)).

Características del algoritmo de coincidencia de cadenas ingenuas

El algoritmo de coincidencia de cadenas está diseñado para encontrar todas las ocurrencias de un patrón dado en un texto.

Estas son las principales características del algoritmo.

1. Es el método más simple entre todos para buscar patrones en un texto de entrada. Comprueba todos los caracteres uno por uno en la cadena de caracteres dada.
2. Encuentra las coincidencias de cadenas exactas, ya sean ocurrencias más o más exactas del patrón.
3. Se usa más cuando hay texto pequeño. Además, no requiere ninguna fase de preprocesamiento.
4. Este método de búsqueda no ocupa espacio extra para trabajar y buscar los patrones en la cadena.

Lea también: Estructura de datos y algoritmo en Python

Ventajas de la búsqueda de patrones Naive

1. No se requieren fases de procesamiento previo en el enfoque de búsqueda ingenua, ya que su tiempo de ejecución es igual al tiempo de coincidencia.
2. No se necesita espacio operativo adicional.
3. Las comparaciones de los patrones con las cadenas se pueden realizar en cualquier orden.

Desventajas de la coincidencia de cadenas ingenuas

Solo hay una desventaja del enfoque ingenuo de coincidencia de cadenas, que es que es ineficiente. Esto se debe a que cuando ha encontrado una posición, no la vuelve a utilizar para encontrar la otra posición. Vuelve al punto de partida y vuelve a buscar el patrón. Y así, no vuelve a utilizar la información del turno anterior.

Conclusión

El algoritmo de comparación de cadenas ingenuas es el enfoque más preferido para encontrar las posiciones de dichos patrones en un texto dado por varias razones, como no requiere procesamiento previo, no hay espacio adicional para la operación, etc. Sin embargo, no se puede usar para textos más grandes porque de su ineficiencia para realizar grandes operaciones más rápido.

Esperamos que esta publicación le haya dado una idea sustancialmente buena sobre el enfoque de búsqueda de patrones ingenuos en python. Para conocer los usos de este enfoque y obtener una comprensión más amplia del tema, póngase en contacto con los expertos de upGrad. Tenemos cursos especialmente diseñados para personas que buscan expandir sus habilidades. ¡Comuníquese con nosotros hoy!

Si está interesado en obtener más información sobre IA, aprendizaje automático, consulte el Diploma PG de IIIT-B y upGrad en Aprendizaje automático e IA, que está diseñado para profesionales que trabajan y ofrece más de 450 horas de capacitación rigurosa, más de 30 estudios de casos y asignaciones, Estado de ex alumnos de IIIT-B, más de 5 proyectos prácticos finales y asistencia laboral con las mejores empresas.