08 Búsqueda en Texto.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 8 Búsqueda en Texto\n",
    "\n",
    "La búsqueda de patrones en un texto es un problema muy importante en la práctica. Sus aplicaciones en computación son variadas, como por ejemplo la búsqueda de una palabra en un archivo de texto o problemas relacionados con biología computacional, en donde se requiere buscar patrones dentro de una secuencia de ADN, la cual puede ser modelada como una secuencia de caracteres (el problema es más complejo que lo descrito, puesto que se requiere buscar patrones en donde ocurren alteraciones con cierta probabilidad, esto es, la búsqueda no es exacta).\n",
    "\n",
    "En este capítulo se considerará el problema de buscar la ocurrencia de un patrón dentro de un texto. Se utilizarán las siguientes convenciones:\n",
    "\n",
    "* $n$ denotará el largo del texto en donde se buscará el patrón, es decir, el texto es $a_0 a_1 \\ldots a_{n-1}$\n",
    "* $m$ denotará el largo del patrón a buscar, es decir el patrón es $b_0 b_1 \\ldots b_{m-1}$\n",
    "\n",
    "Por ejemplo:\n",
    "\n",
    "* Texto = \"analisis de algoritmos\"\n",
    "* Patrón = \"algo\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Algoritmo de fuerza bruta\n",
    "\n",
    "Se alinea la primera posición del patrón con la primera posición del texto, y se comparan los caracteres uno a uno hasta que se acabe el patrón, en cuyo caso se encontró una ocurrencia del patrón en el texto, o hasta que se encuentre una discrepancia.\n",
    "\n",
    "![bruta1](bruta1.png)\n",
    "\n",
    "Si se detiene la búsqueda por una discrepancia, se desliza el patrón en una posición hacia la derecha y se intenta calzar el patrón nuevamente.\n",
    "\n",
    "![bruta2](bruta2.png)\n",
    "\n",
    "El proceso se repite, siempre avanzando en una posición\n",
    "\n",
    "![bruta3](bruta3.png)\n",
    "\n",
    "hasta que finalmente se encuentre\n",
    "\n",
    "![bruta4](bruta4.png)\n",
    "\n",
    "o se agote el texto sin encontra el patrón.\n",
    "\n",
    "En el peor caso este algoritmo realiza $\\Theta(mn)$ comparaciones de caracteres.\n",
    "\n",
    "Si suponemos que todos los caracteres aparecen en forma equiprobable e independiente, en el caso esperado el método de fuerza bruta funciona mucho mejor. Si el alfabeto es de tamaño $c$, entonces en cada comparación la probabilidad de que dos caracteres sean iguales es $\\frac{1}{c}$ y de que sean distintos es $1-\\frac{1}{c}$. A partir de cada posición, el número esperado de comparaciones que se efectúa hasta encontrar un descalce es\n",
    "\n",
    "$$\n",
    "\\frac{1}{1-\\frac{1}{c}}=\\frac{c}{c-1}= 1+\\frac{1}{c-1}\n",
    "$$\n",
    "\n",
    "Por lo tanto, en cada posición en que el patrón no está, el número esperado de comparaciones es una constante poco mayor que $1$, por lo tanto el costo total de la búsqueda es $\\Theta(n)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Algoritmo Knuth-Morris-Pratt (KMP)\n",
    "\n",
    "Suponga que se está comparando el patrón y el texto en una posición dada, cuando se encuentra una discrepancia.\n",
    "\n",
    "![kmp1](kmp1.png)\n",
    "\n",
    "Sea $x$ la parte del patrón que calza con el texto, e $y$ la correspondiente parte del texto, y suponga que el largo de $x$ es $j$. El algoritmo de fuerza bruta mueve el patrón una posición hacia la derecha, sin embargo, esto puede o no puede ser lo correcto en el sentido que los primeros $j-1$ caracteres de $x$ pueden o no pueden calzar los últimos $j-1$ caracteres de $y$.\n",
    "\n",
    "La observación clave que realiza el algoritmo Knuth-Morris-Pratt (en adelante KMP) es que $x$ es igual a $y$, por lo que la pregunta planteada en el párrafo anterior puede ser respondida mirando solamente el patrón de búsqueda, lo cual permite precalcular la respuesta y almacenarla en una tabla.\n",
    "\n",
    "Por lo tanto, si deslizar el patrón en una posición no funciona, se puede intentar deslizarlo en $2, 3, \\ldots,$ hasta $j$ posiciones.\n",
    "\n",
    "Se define la *función de fracaso* (*failure function*) del patrón como:\n",
    "\n",
    "$$\n",
    "f(j)=\\max\\{i | 0 \\le i<j \\wedge b_0\\ldots b_{i-1} = b_{j-i-1}\\ldots b_{j-1} \\}\n",
    "$$\n",
    "\n",
    "![kmp2](kmp2.png)\n",
    "\n",
    "Intuitivamente, $f(j)$ es el largo del mayor prefijo de $x$ que además es sufijo del mismo $x$.\n",
    "Por ejemplo, si el patrón es ``\"aabaaa\"``, entonces la función de fracaso es\n",
    "\n",
    "$j$    | 1 | 2 | 3 | 4 | 5 | 6\n",
    "------ | - | - | - | - | - | -\n",
    "$f(j)$ | 0 | 1 | 0 | 1 | 2 | 2\n",
    "\n",
    "\n",
    "Si se detecta una discrepancia entre el patrón y el texto cuando se trata de calzar $b_j$, se desliza el patrón de manera que $b_{f(j)-1}$ se encuentre donde $b_{j-1}$ se encontraba, y se intenta calzar nuevamente.\n",
    "\n",
    "![kmp3](kmp3.png)\n",
    "\n",
    "En el siguiente ejemplo mostramos la ejecución de una búsqueda:\n",
    "\n",
    "![kmp4](kmp4.png)\n",
    "\n",
    "Suponiendo que se tiene la función $f(j)$ precalculado, la implementación del algoritmo KMP es la siguiente:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "def kmp(a,b,f): # busca b dentro de a, retorna None (fracaso) o posición del calce\n",
    "    n=len(a)\n",
    "    m=len(b)\n",
    "    j=0\n",
    "    for k in range(0,n):\n",
    "        if j==m:\n",
    "            return k-m # éxito\n",
    "        while j>0 and a[k]!=b[j]:\n",
    "            j=f[j]\n",
    "        if a[k]==b[j]:\n",
    "            j=j+1\n",
    "    return None # fracaso"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5\n",
      "None\n"
     ]
    }
   ],
   "source": [
    "f=[0,0,1,0,1,2,2]\n",
    "print(kmp(\"aaaabaabaaabb\",\"aabaaa\",f))\n",
    "print(kmp(\"aaaabaabaaabb\",\"abbaaa\",f))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "El tiempo de ejecución de este algoritmo no es difícil de analizar, pero es necesario ser cuidadoso al hacerlo. Dado que se tienen dos ciclos anidados, se puede acotar el tiempo de ejecución como el número de veces que se ejecuta el ciclo externo (menor o igual a $n$) multiplicado por el número de veces que se ejecuta el ciclo interno (menor o igual a $m$), lo que de una cota superior a $O(mn)$, ¡que es igual a lo que demora el algoritmo de fuerza bruta!.\n",
    "\n",
    "Sin embargo, el análisis descrito es pesimista. Observemos que el número total de veces que el ciclo interior es ejecutado es menor o igual al número de veces que se puede decrementar $j$, dado que $f(j)<j$. Pero $j$ comienza desde cero y es siempre mayor o igual que cero, por lo que dicho número es menor o igual al número de veces que $j$ es incrementado, el cual es menor que $n$. Por lo tanto, el tiempo total de ejecución es $\\Theta(n)$ en el peor caso. Por otra parte, $k$ nunca es decrementado, lo que implica que el algoritmo nunca se devuelve en el texto."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Cálculo de la función de fracaso\n",
    "\n",
    "Queda por resolver el problema de definir la función de fracaso, $f(j)$. Esto se puede realizar inductivamente. Para empezar, $f(1)=0$ por definición. Para calcular $f(j+1)$ suponga que ya se tienen almacenados los valores de $f(1), f(2), \\ldots, f(j)$. Se desea encontrar un $i$ tal que el $i$-ésimo carácter del patrón sea igual al $j$-ésimo carácter del patrón.\n",
    "\n",
    "Para esto se debe cumplir que $i=f(j)$. Si $b_i=b_j$, entonces $f(j+1)=i+1$. En caso contrario, se reemplaza $i$ por $f(i)$ y se verifica nuevamente la condición.\n",
    "\n",
    "![kmp5](kmp5.png)\n",
    "\n",
    "El algoritmo resultante es el siguiente (note que es similar al algoritmo KMP):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "def fracaso(b): # calcula y retorna función de fracaso para patrón b\n",
    "    m=len(b)\n",
    "    f=[0]*(m+1)\n",
    "    for j in range(1,m):\n",
    "        i=f[j]\n",
    "        while i>0 and b[i]!=b[j]:\n",
    "            i=f[i]\n",
    "        if b[i]==b[j]:\n",
    "            f[j+1]=i+1\n",
    "        else:\n",
    "            f[j+1]=0\n",
    "    return f"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0, 0, 1, 0, 1, 2, 2]\n"
     ]
    }
   ],
   "source": [
    "print(fracaso(\"aabaaa\"))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "El tiempo de ejecución para calcular la función de fracaso puede ser acotado por los incrementos y decrementos de la variable $i$, y por lo tanto es $\\Theta(m)$.\n",
    "\n",
    "Por lo tanto, el tiempo total de ejecución del algoritmo en el peor caso, sumando el preprocesamiento del patrón más la búsqueda, es $\\Theta(m+n)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Algoritmo de Boyer-Moore\n",
    "\n",
    "Hasta el momento, los algoritmos de búsqueda en texto siempre comparan el patrón con el texto de izquierda a derecha. La idea del algoritmo de Boyer-Moore es comparar *de derecha a izquierda*: si hay una discrepancia en el último carácter del patrón y el carácter del texto no aparece en todo el patrón, entonces éste se puede deslizar $m$ posiciones sin realizar ninguna comparación extra. En particular, no habría sido necesario comparar los primeros $m-1$ caracteres del texto, lo cual indica que se podría realizar una búsqueda en el texto con menos de $n$ comparaciones; sin embargo, si el carácter discrepante del texto se encuentra dentro del patrón, éste podría desplazarse en un número menor de espacios.\n",
    "\n",
    "El método descrito es la base del algoritmo Boyer-Moore, del cual se estudiarán dos variantes: Horspool y Sunday."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Algoritmo Boyer-Moore-Hospool (BMH)\n",
    "\n",
    "Supongamos que el último caracter del patrón de búsqueda $b$ se encuentra alineado con el caracter $a_k$ del texto.\n",
    "El algoritmo BMH compara el patrón con el texto **de derecha a izquierda**, y se detiene cuando se encuentra una discrepancia con el texto. Cuando esto sucede, se desliza el patrón de manera que la letra $c=a_k$ del texto que estaba alineada con la letra final del patrón, ahora quede alineada con un caracter anterior de $b$ con el cual coincida, si dicho calce es posible, o si no, con $b_{-1}$, un carácter ficticio a la izquierda de $b_0$ (este es el mejor caso del algoritmo).\n",
    "\n",
    "Para determinar el desplazamiento del patrón se define la función $g(c)$ como:\n",
    "\n",
    "* $g(c)=i$ si $i$ es el mayor subíndice en el rango $0\\le i \\le m-2$ tal que $b_i=c$. Nótese que si hay más de una ocurrencia de $c$, se toma la de más a la derecha.\n",
    "\n",
    "![bmh1](bmh1.png)\n",
    "\n",
    "* $g(c)=-1$ si $c$ no aparece entre los primeros $m-1$ caracteres del patrón.\n",
    "\n",
    "![bmh2](bmh2.png)\n",
    "\n",
    "En ambos casos se busca el caracter $c$ solo dentro de los primeros $m-1$ caracteres del patrón, excluyendo el último, para que el deslizamiento del patrón sea de al menos una posición.\n",
    "\n",
    "Esta función sólo depende del patrón y se puede precalcular antes de realizar la búsqueda."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Ejemplo de Boyer-Moore-Horspool\n",
    "\n",
    "Supongamos que queremos buscar el patrón ``\"datos\"`` dentro de ``\"estructuras de datos\"``. La función $g(c)$ estaría dada por\n",
    "\n",
    "$c$    | \"a\" | \"d\" | \"o\" | \"t\"\n",
    "------ | --- | --- | --- | ---\n",
    "$g(c)$ |  1  |  0  |  3  |  2\n",
    "\n",
    "y $g(c)=-1$ para toda otra letra $c$.\n",
    "\n",
    "El siguiente diagrama muestra el proceso de búsqueda:\n",
    "\n",
    "![bmh3](bmh3.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Por simplicidad de programación, para implementar el algoritmo usaremos un diccionario de Python para la función $g$. En una implementación eficiente, esta función se impelemntaría como un arreglo subindicado por la representación numérica de cada letra."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {},
   "outputs": [],
   "source": [
    "def construyeg(b): # construye un diccionario para representar la función g\n",
    "    d={}\n",
    "    for i in range(0,len(b)-1): # ignoramos el último caracter\n",
    "        d[b[i]]=i\n",
    "    return d"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {},
   "outputs": [],
   "source": [
    "def bmh(a,b): # busca b dentro de a, retorna None (fracaso) o posición del calce\n",
    "    g=construyeg(b) # Uso: g(c)=g.get(c,-1) para rellenar con -1 los valores faltantes\n",
    "    n=len(a)\n",
    "    m=len(b)\n",
    "    k=m-1\n",
    "    j=m-1\n",
    "    while k<n:\n",
    "        if j<0:\n",
    "            return k-m+1\n",
    "        if a[k-(m-1-j)]==b[j]:\n",
    "            j=j-1\n",
    "        else:\n",
    "            k=k+(m-1-g.get(a[k],-1))\n",
    "            j=m-1\n",
    "    return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "15\n",
      "1\n",
      "None\n"
     ]
    }
   ],
   "source": [
    "print(bmh(\"estructuras de datos\",\"datos\"))\n",
    "print(bmh(\"estructuras de datos\",\"struct\"))\n",
    "print(bmh(\"estructuras de datos\",\"gatos\"))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Se puede demostrar que si el alfabeto tiene tamaño $L$ y los caracteres aparecen con probabilidad uniforme y de manera independiente, entonces el tiempo promedio que demora BMH es\n",
    "\n",
    "$$\n",
    "\\Theta\\left( n \\left( \\frac{1}{m}+\\frac{1}{2L} \\right) \\right)\n",
    "$$\n",
    "\n",
    "Para un alfabeto razonablemente grande, esto es aproximadamente $\\Theta\\left( \\frac{n}{m} \\right)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Algoritmo Boyer-Moore-Sunday (BMS)\n",
    "\n",
    "El algoritmo BMH desliza el patrón basado en el símbolo del texto que corresponde a la posición del último carácter del patrón. Este siempre se desliza al menos una posición si se encuentra una discrepancia con el texto.\n",
    "\n",
    "Es fácil ver que si se utiliza el carácter una posición más adelante en el texto como entrada de la función siguiente el algoritmo también funciona, pero en este caso es necesario considerar el patrón completo al momento de calcular los valores de la función siguiente. Esta variante del algoritmo es conocida como Boyer-Moore-Sunday (BMS).\n",
    "\n",
    "Caso en que $c=a_{k+1}$ aparece dentro del patrón:\n",
    "\n",
    "![bms1](bms1.png)\n",
    "\n",
    "Caso en que $c=a_{k+1}$ no aparece dentro del patrón:\n",
    "\n",
    "![bms2](bms2.png)\n",
    "\n",
    "#### Ejemplo de Boyer-Moore-Sunday\n",
    "\n",
    "Supongamos que queremos buscar el patrón ``\"datos\"`` dentro de ``\"estructuras de datos\"``. La función $g(c)$ estaría dada por\n",
    "\n",
    "$c$    | \"a\" | \"d\" | \"o\" | \"s\" | \"t\"\n",
    "------ | --- | --- | --- | --- | ---\n",
    "$g(c)$ |  1  |  0  |  3  |  4  |  2\n",
    "\n",
    "y $g(c)=-1$ para toda otra letra $c$.\n",
    "\n",
    "El siguiente diagrama muestra el proceso de búsqueda:\n",
    "\n",
    "![bms3](bms3.png)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {},
   "outputs": [],
   "source": [
    "def construyeg(b): # construye un diccionario para representar la función g\n",
    "    d={}\n",
    "    for i in range(0,len(b)): # utilizamos hasta el último caracter\n",
    "        d[b[i]]=i\n",
    "    return d"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "metadata": {},
   "outputs": [],
   "source": [
    "def bms(a,b): # busca b dentro de a, retorna None (fracaso) o posición del calce\n",
    "    g=construyeg(b) # Uso: g(c)=g.get(c,-1) para rellenar con -1 los valores faltantes\n",
    "    n=len(a)\n",
    "    m=len(b)\n",
    "    k=m-1\n",
    "    j=m-1\n",
    "    while k<n:\n",
    "        if j<0:\n",
    "            return k-m+1\n",
    "        if a[k-(m-1-j)]==b[j]:\n",
    "            j=j-1\n",
    "        else:\n",
    "            if k>=n-1:\n",
    "                break\n",
    "            k=k+(m-g.get(a[k+1],-1))\n",
    "            j=m-1\n",
    "    return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "15\n",
      "1\n",
      "None\n"
     ]
    }
   ],
   "source": [
    "print(bms(\"estructuras de datos\",\"datos\"))\n",
    "print(bms(\"estructuras de datos\",\"struct\"))\n",
    "print(bms(\"estructuras de datos\",\"gatos\"))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}