Búsqueda de patrones para niños

La búsqueda de patrones en la informática es como buscar una forma o un dibujo específico dentro de un conjunto de piezas o datos. Imagina que tienes un montón de piezas de LEGO y quieres encontrar todas las que tienen una forma de estrella. Eso es la búsqueda de patrones.

A diferencia del reconocimiento de patrones, donde se buscan cosas parecidas pero no exactamente iguales, en la búsqueda de patrones la coincidencia suele ser exacta. Los patrones pueden ser secuencias de letras o números (como una palabra en un texto) o estructuras más complejas, como un árbol genealógico.

Esta técnica se usa para encontrar dónde aparece un patrón, para sacar una parte de ese patrón o para reemplazarlo por otra cosa. Por ejemplo, en un editor de texto, puedes buscar todas las veces que aparece la palabra "casa" y cambiarla por "hogar".

Los patrones en secuencias, como el texto, a menudo se describen usando algo llamado expresiones regulares.

En algunos lenguajes de programación, como Haskell o ML, los patrones se usan para organizar y procesar datos según su estructura. Esto hace que sea más fácil trabajar con información compleja.

¿Qué es la búsqueda de patrones?

La búsqueda de patrones es una técnica fundamental en la informática. Consiste en encontrar una secuencia o estructura específica dentro de un conjunto de datos más grande. Piensa en ello como un juego de "encuentra las diferencias", pero en este caso, buscas las "similitudes exactas".

¿Cómo funciona la búsqueda de patrones?

Cuando un programa realiza una búsqueda de patrones, compara el patrón que le has dado con las partes de los datos. Si una parte de los datos coincide exactamente con el patrón, el programa puede hacer algo con esa parte, como mostrarla, guardarla o cambiarla.

Patrones de secuencia: buscando en el texto

Los patrones de secuencia son los más comunes. Se usan para buscar en textos, como cuando usas la función de "buscar" en un documento. Por ejemplo, si buscas la palabra "sol", el programa revisa el texto hasta encontrar esa secuencia de letras. Las expresiones regulares son herramientas especiales que nos permiten describir patrones de texto muy complejos, como "cualquier palabra que empiece con 'a' y termine con 'o'".

Patrones de árbol: organizando la información

Los patrones de árbol se usan para datos que tienen una estructura jerárquica, como un árbol genealógico o la forma en que se organizan los archivos en tu computadora (carpetas dentro de carpetas). Estos patrones ayudan a los programas a entender cómo se relacionan las diferentes partes de la información.

Historia de la búsqueda de patrones

La idea de buscar patrones en datos no es nueva. Los primeros programas de computadora que usaron esta técnica fueron los editores de texto.

Los inicios en los editores de texto

En los años 60, en los laboratorios Bell, un científico llamado Ken Thompson mejoró un editor de texto llamado QED. Le añadió la capacidad de buscar y reemplazar texto usando expresiones regulares. Esto fue un gran avance porque permitía a los usuarios encontrar y cambiar texto de formas muy específicas y potentes.

Lenguajes de programación pioneros

Después, algunos lenguajes de programación empezaron a incluir la búsqueda de patrones como una característica principal.

• SNOBOL, creado en 1962, fue uno de los primeros. Era muy bueno para manipular texto.
• Otros lenguajes como SASL (1976), NPL (1977) y KRC (1981) también incorporaron estas ideas.
• En 1970, una extensión del lenguaje LISP fue el primer lenguaje en usar patrones basados en estructuras de árbol.

Tipos de patrones básicos

Los patrones más sencillos son un valor específico o una variable.

Patrones de valor y variables

Imagina que tienes una función que hace algo solo si le das el número 0. En un lenguaje como Haskell, se vería así:

 f 0 = 1

Aquí, el `0` es un patrón de valor. La función solo funciona si el número que le das es exactamente 0. Si le das cualquier otro número, no coincide.

Pero también podemos hacer que la función sea más general usando una variable:

 f n = n * f (n-1)

En este caso, `n` es un patrón de variable. Coincide con cualquier número que le des y le da ese nombre (`n`) para usarlo en la función. Así, la función puede trabajar con cualquier número.

El patrón comodín

Existe un patrón especial llamado "comodín", que a menudo se escribe como `_` (un guion bajo). Este patrón es como un "cualquiera". Coincide con cualquier valor, pero no le da un nombre. Es útil cuando no te importa el valor exacto, solo que haya algo ahí.

Patrones de árbol: estructuras complejas

Los patrones de árbol nos permiten describir partes de estructuras de datos más complejas, como los árboles. Piensa en cómo se organizan los datos en un programa, a menudo como un árbol de sintaxis abstracta o tipos de datos algebraicos.

Ejemplo de patrón de árbol con colores

En Haskell, puedes definir un tipo de dato para un color que guarde un número entero y un texto:

 data Color = ColorConstructor Integer String

Aquí, `ColorConstructor` es como un nodo en un árbol, y el número entero y el texto son sus "ramas" o "hojas".

Si queremos sacar solo el número entero de un color, podemos usar un patrón de árbol:

 integerPart (ColorConstructor theInteger _) = theInteger

Este patrón dice: "Si el dato es un `ColorConstructor` que tiene un número (al que llamaremos `theInteger`) y luego cualquier otra cosa (el `_` comodín), entonces dame `theInteger`".

Filtrado de datos con patrones

La búsqueda de patrones es muy útil para filtrar datos, es decir, para seleccionar solo los datos que cumplen ciertas características.

Filtrando listas con patrones

Imagina que tienes una lista de elementos y quieres quedarte solo con los que tienen una forma específica. En Haskell, puedes hacerlo así:

 [A x|A x <- [A 1, B 1, A 2, B 2]]

Esto significa: "De la lista `[A 1, B 1, A 2, B 2]`, dame solo los elementos que tienen la forma `A x`". El resultado sería: `[A 1, A 2]` Porque solo `A 1` y `A 2` coinciden con el patrón `A x`.

Búsqueda de patrones en Mathematica

Mathematica es un programa que usa mucho la búsqueda de patrones. En Mathematica, todo se ve como un árbol.

Cómo se usan los patrones en Mathematica

En Mathematica, un patrón se crea poniendo un `_` (guion bajo) en las posiciones donde quieres que haya "cualquier cosa". Por ejemplo, el patrón `A[_]` coincidirá con `A[1]`, `A[2]` o `A[cualquier_cosa]`. La `A` es la parte fija, y el `_` es la parte que puede variar.

La función `Cases` en Mathematica es muy útil para filtrar. Por ejemplo: `Cases[{a[1], b[1], a[2], b[2]}, a[_] ]` Esto busca en la lista los elementos que coincidan con el patrón `a[_]` y devuelve: `{a[1], a[2]}`

Rastreo de cálculos con patrones

Mathematica también puede usar patrones para ver cómo se desarrollan los cálculos. Por ejemplo, si defines la secuencia de Fibonacci, puedes usar la función `Trace` para ver todas las llamadas a la función `fib` que se hacen para calcular un número: `Trace[fib[3], fib[_]]` Esto te mostrará cómo `fib[3]` se descompone en `fib[2]` y `fib[1]`, y así sucesivamente.

Búsqueda de patrones y cadenas de texto

Una de las aplicaciones más comunes de la búsqueda de patrones es con las cadenas de texto (secuencias de letras y números).

Patrones de árbol para cadenas

En lenguajes como Haskell, las cadenas de texto se pueden ver como listas de caracteres. Una lista se define como una lista vacía o un elemento seguido de otra lista. Por ejemplo:

 [] -- una lista vacía
 x:xs -- un elemento 'x' seguido de una lista 'xs'

Esto nos permite crear patrones para las cadenas. Si queremos la primera letra de una cadena, podemos escribir una función así:

 head (element:_) = element

Este patrón dice: "Si la cadena tiene un primer `element` y luego cualquier otra cosa (`_`), dame ese `element`".

Ejemplos de patrones de cadena

En Mathematica, puedes combinar diferentes tipos de caracteres en un patrón. Por ejemplo: `StringExpression[LetterCharacter, DigitCharacter]` Este patrón coincidirá con una cadena que empiece con una letra y luego tenga un número.

En Haskell, podrías lograr algo similar usando "guardas", que son condiciones adicionales:

 [letter, digit] | isAlpha letter && isDigit digit

Esto significa: "Si tengo una lista con dos elementos, `letter` y `digit`, y `letter` es una letra y `digit` es un número, entonces coincide".

SNOBOL: un lenguaje para patrones

SNOBOL (que significa "Lenguaje Simbólico Orientado a Cadenas") fue un lenguaje de programación desarrollado en los laboratorios Bell entre 1962 y 1967.

Características de SNOBOL

Lo que hacía especial a SNOBOL era que los patrones eran un tipo de dato muy importante. Podías manipular patrones como si fueran números o textos. También tenía operadores para unir patrones o para buscar una alternativa entre varios patrones.

SNOBOL fue muy popular en las universidades de Estados Unidos en los años 60 y 70, y se usó mucho para manipular texto en áreas como las humanidades. Aunque hoy en día lenguajes como Perl y Awk son más conocidos por sus expresiones regulares, los patrones de SNOBOL eran incluso más potentes en algunos aspectos.

Véase también

En inglés: Pattern matching Facts for Kids