demo.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Árvore Patrícia"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Apresentação para o seminário da disciplina Projeto de Algoritmos II**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Integrantes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- Eduardo Gil Serrão Cardoso\n",
    "- Gabriela Souza Maximino\n",
    "- Igor Matheus Souza Moreira\n",
    "- Marco Aurélio Lima do Nascimento Júnior"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Agenda"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- [Introdução](#Introdução)\n",
    "    - [Pesquisa Digital](#Pesquisa-Digital)\n",
    "    - [O que é PATRICIA?](#O-que-é-a-PATRICIA?)\n",
    "- [A árvore PATRICIA](#A-árvore-PATRICIA)\n",
    "    - [Visão Geral](#Visão-Geral)\n",
    "    - [Disclaimer](#Disclaimer)\n",
    "    - [Definições e Propriedades](#Definições-e-Propriedades)\n",
    "        - [Classe Node](#Classe-Node)\n",
    "        - [Classe Arvore](#Classe-Arvore)\n",
    "    - [Na prática](#Na-prática)\n",
    "        - [Exemplo de uso](#Exemplo-de-uso)\n",
    "        - [Teste de confiabilidade](#Teste-de-confiabilidade)\n",
    "- [Complexidade das operações](#Complexidade-das-operações)\n",
    "- [Comparação com outras estruturas de dados](#Comparação-com-outras-estruturas-de-dados)\n",
    "- [Aplicações](#Aplicações)\n",
    "- [Conclusões]()\n",
    "- [Referências]()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Introdução"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- Tem-se uma maior capacidade de armazenamento em dispositivos de memória (primária e secundária);\n",
    "- Arquivos de grande conteúdo (que estão na RAM) puderam ser manipulados;\n",
    "\n",
    "\n",
    "- **Problema:** como recuperar uma informação em meio a tantas dentro desse arquivo?\n",
    "- **Solução:** métodos de pesquisa: sequencial, binária… e **pesquisa digital!**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Voltar ao topo](#Árvore-Patrícia)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Pesquisa Digital"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- Arquivos são divididos em registros. Cada registro possui uma chave;\n",
    "- O **objetivo das pesquisas** em geral é encontrar, baseado em uma chave de busca, chaves iguais no arquivo;\n",
    "- A busca digital consiste em representar essas chaves como dígitos, podendo ser divisíveis;\n",
    "- A estrutura básica para uma pesquisa digital é a árvore digital;\n",
    "- As árvores digitais também são conhecidas como Trie (re**TRIE**val);\n",
    "- A **árvore PATRICIA** é uma árvore digital!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Voltar ao topo](#Árvore-Patrícia)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### O que é a PATRICIA?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- Acrônimo para ***P*** *ractical* ***A*** *lgorithm* ***t*** *o* ***R*** *etrieve* ***I*** *nformation* ***C*** *oded* ***i*** *n* ***A*** *lphanumeric* (Algoritmo Prático para Recuperar Informação Codificada em Alfanumérico);\n",
    "- Criada por Donald R. Morrison em 1968 (referência abaixo);\n",
    "- Implementação eficiente da árvore digital binária.\n",
    "\n",
    "Morrison, D. R. (1968). PATRICIA—practical algorithm to retrieve information coded in alphanumeric. Journal of the ACM (JACM), 15(4), 514-534."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Voltar ao topo](#Árvore-Patrícia)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## A árvore PATRICIA"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Visão Geral"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Usaremos as sete palavras **casco**, **cascalho**, **cascata**, **dama**, **domando**, **dominar** e **domínio** para representar as árvores."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- **Árvore Trie:** cada nível representa um caractere\n",
    "    - **Problema:** gera muitos nós.\n",
    "    \n",
    "![](imagens/exemplo_de_trie.png)\n",
    "    \n",
    "- **Árvore Radix:** árvore de prefixos.\n",
    "    - **Melhoria:** diminui o número de nós criados.\n",
    "    \n",
    "![](imagens/exemplo_de_radix.png)\n",
    "    \n",
    "- **Árvore Patrícia:** uma árvore Trie compacta... em algumas definições.\n",
    "\n",
    "![](imagens/exemplo_de_patricia.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Voltar ao topo](#Árvore-Patrícia)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### *Disclaimer*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Algumas definições diferentes foram encontradas:\n",
    "- PATRICIA enquanto árvore Trie compacta;\n",
    "- PATRICIA enquanto variação da árvore Radix 2 (Radix binária).\n",
    "\n",
    "Optamos por nos ater à definição de árvore PATRICIA como variação de árvore Trie.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Voltar ao topo](#Árvore-Patrícia)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Definições e Propriedades"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- Estritamente binária;\n",
    "- Filhos unários de nós são compactados com seus respectivos pais;\n",
    "- Cada nó guarda a posição da chave a partir da qual as sub-árvores começam a se diferenciar, possibilitando as comparações;\n",
    "- As chaves são guardadas apenas nos nós-folha.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Voltar ao topo](#Árvore-Patrícia)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Classe `Node`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Node:\n",
    "\n",
    "    def __init__(self, pos, val, prefixo):\n",
    "\n",
    "        \"\"\"\n",
    "        Unidade basica\n",
    "        :param int pos:\n",
    "        :param str val:\n",
    "        :param str prefixo:\n",
    "        \"\"\"\n",
    "\n",
    "        self.filhos = [None, None]\n",
    "\n",
    "        self.prefixo = prefixo\n",
    "        \n",
    "        self.pos = pos\n",
    "        \n",
    "        self.val = ord(val)\n",
    "\n",
    "    def get(self, palavra):\n",
    "\n",
    "        if palavra[:self.pos] != self.prefixo or len(palavra) <= self.pos: return 0\n",
    "\n",
    "        valor = ord(palavra[self.pos])\n",
    "\n",
    "        if valor <= self.val:\n",
    "\n",
    "            return self.filhos[0]\n",
    "\n",
    "        return self.filhos[1]\n",
    "\n",
    "\n",
    "    def derivados(self):\n",
    "\n",
    "        derivados = []\n",
    "\n",
    "        for i in self.filhos:\n",
    "\n",
    "            if type(i) == str: derivados.append(i[:-1])\n",
    "\n",
    "            else: derivados += i.derivados()\n",
    "\n",
    "        return derivados\n",
    "\n",
    "\n",
    "    def __repr__(self):\n",
    "\n",
    "        return \"[{}|{}]\".format(self.pos, chr(self.val))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Voltar ao topo](#Árvore-Patrícia)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Classe `Arvore`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Arvore:\n",
    "\n",
    "    def __init__(self, raiz):\n",
    "\n",
    "        \"\"\"\n",
    "        Inicia a árvore\n",
    "        :param str raiz:\n",
    "        \"\"\"\n",
    "\n",
    "        self.raiz = raiz + \"$\"\n",
    "\n",
    "\n",
    "    def get_intersect(self, p1, p2):\n",
    "\n",
    "        \"\"\"\n",
    "        Buca o ponto onde duas strings de diferenciam\n",
    "        :param str p1:\n",
    "        :param str p2:\n",
    "        :return int:\n",
    "        \"\"\"\n",
    "        for i in range(len(p1)):\n",
    "\n",
    "            if len(p2) > i:\n",
    "\n",
    "                if p1[i] != p2[i]: return i\n",
    "\n",
    "\n",
    "    def insere(self, palavra):\n",
    "\n",
    "        \"\"\"\n",
    "        Insere uma string na árvore\n",
    "        :param str palavra:\n",
    "        :return None:\n",
    "        \"\"\"\n",
    "\n",
    "        # print(\"Inserindo %s\" % palavra)\n",
    "\n",
    "        if self.check(palavra):\n",
    "\n",
    "            print(\"[Erro] Palavra já inserida\")\n",
    "            \n",
    "            return\n",
    "\n",
    "        palavra += '$'\n",
    "\n",
    "        pai = None\n",
    "        \n",
    "        node = self.raiz\n",
    "        \n",
    "        i = 0\n",
    "\n",
    "        while 1:\n",
    "\n",
    "            # Caso nó folha\n",
    "\n",
    "            if type(node) == str:\n",
    "\n",
    "                pos = self.get_intersect(palavra, node)\n",
    "                \n",
    "                # Caso nó folha é raiz também\n",
    "\n",
    "                if pai is None:\n",
    "\n",
    "                    l = sorted([(ord(palavra[pos]), palavra), (ord(node[pos]),node)])\n",
    "                    \n",
    "                    self.raiz = Node(pos, chr(l[0][0]), l[0][1][:pos])\n",
    "                    \n",
    "                    self.raiz.filhos = [k[1] for k in l]\n",
    "\n",
    "                    return\n",
    "\n",
    "\n",
    "                # Caso padrão\n",
    "\n",
    "                else:\n",
    "\n",
    "                    lado = pai.filhos.index(node)\n",
    "\n",
    "                    l = sorted([(ord(palavra[pos]), palavra), (ord(node[pos]),node)])\n",
    "\n",
    "                    pai.filhos[lado] = Node(pos, chr(l[0][0]), l[0][1][:pos])\n",
    "                    \n",
    "                    pai.filhos[lado].filhos = [k[1] for k in l]\n",
    "\n",
    "                    return\n",
    "\n",
    "\n",
    "\n",
    "            else:\n",
    "\n",
    "                prox = node.get(palavra)\n",
    "\n",
    "                # Caso prefixo não combina\n",
    "\n",
    "                if not prox:\n",
    "\n",
    "                    pos = self.get_intersect(palavra, node.prefixo)\n",
    "\n",
    "                    l = sorted([(ord(palavra[pos]), palavra), (ord(node.prefixo[pos]),node)])\n",
    "\n",
    "                    # Caso raiz\n",
    "\n",
    "                    if pai is None:\n",
    "\n",
    "                        self.raiz = Node(pos, chr(l[0][0]), palavra[:pos])\n",
    "\n",
    "                        self.raiz.filhos = [k[1] for k in l]\n",
    "\n",
    "                        return\n",
    "\n",
    "                    else:\n",
    "\n",
    "                        lado = pai.filhos.index(node)\n",
    "                        \n",
    "                        pai.filhos[lado] = Node(pos, chr(l[0][0]), palavra[:pos])\n",
    "                        \n",
    "                        pai.filhos[lado].filhos = [k[1] for k in l]\n",
    "\n",
    "                        return\n",
    "\n",
    "                # Base de iteração\n",
    "\n",
    "                else:\n",
    "\n",
    "                    pai = node\n",
    "                    \n",
    "                    node = prox\n",
    "\n",
    "\n",
    "    def check(self, palavra):\n",
    "\n",
    "        palavra += '$'\n",
    "\n",
    "        node = self.raiz\n",
    "\n",
    "        while 1:\n",
    "\n",
    "            if type(node) == str:\n",
    "\n",
    "                return node == palavra\n",
    "\n",
    "            next = node.get(palavra)\n",
    "            \n",
    "            if next:\n",
    "\n",
    "                node = next\n",
    "\n",
    "            else:\n",
    "\n",
    "                return False\n",
    "\n",
    "\n",
    "    def remove(self, palavra):\n",
    "\n",
    "        if not self.check(palavra):\n",
    "\n",
    "            print(\"[Erro] Palavra não encontrada\")\n",
    "            return\n",
    "\n",
    "        palavra += '$'\n",
    "\n",
    "        avo = None\n",
    "        pai = None\n",
    "        node = self.raiz\n",
    "\n",
    "        while 1:\n",
    "\n",
    "            if type(node) == str:\n",
    "\n",
    "                if pai is None:\n",
    "\n",
    "                    print(\"[Erro] Não é possível remover único item da arvore\")\n",
    "                    \n",
    "                    return\n",
    "\n",
    "                else:\n",
    "\n",
    "                    pai.filhos.remove(node)\n",
    "                    \n",
    "                    novo_sucessor = pai.filhos[0]\n",
    "\n",
    "                    if avo is None:\n",
    "\n",
    "                        self.raiz = novo_sucessor\n",
    "                        \n",
    "                        del pai\n",
    "\n",
    "                        return\n",
    "\n",
    "                    else:\n",
    "\n",
    "                        index = avo.filhos.index(pai)\n",
    "                        \n",
    "                        avo.filhos[index] = novo_sucessor\n",
    "                        \n",
    "                        del pai\n",
    "\n",
    "                        return\n",
    "\n",
    "            else:\n",
    "\n",
    "                prox = node.get(palavra)\n",
    "\n",
    "                if pai is None:\n",
    "\n",
    "                    pai = node\n",
    "                    \n",
    "                    node = prox\n",
    "\n",
    "                else:\n",
    "\n",
    "                    avo = pai\n",
    "                    \n",
    "                    pai = node\n",
    "                    \n",
    "                    node = prox\n",
    "\n",
    "    def derivados(self, prefixo):\n",
    "\n",
    "        \"\"\"\n",
    "        Exibe folhas derivadas de determinado prefixo\n",
    "        :param str prefixo:\n",
    "        :return str[]:\n",
    "        \"\"\"\n",
    "\n",
    "        tam = len(prefixo)\n",
    "        \n",
    "        node = self.raiz\n",
    "\n",
    "        while 1:\n",
    "\n",
    "            if type(node) == str:\n",
    "\n",
    "                if node[:tam] == prefixo:\n",
    "\n",
    "                    return [node[:-1]]\n",
    "\n",
    "                else:\n",
    "\n",
    "                    return []\n",
    "\n",
    "            else:\n",
    "\n",
    "                if node.prefixo == prefixo or node.prefixo[:tam] == prefixo:\n",
    "\n",
    "                    return node.derivados()\n",
    "\n",
    "                next = node.get(prefixo)\n",
    "\n",
    "                if next:\n",
    "                    \n",
    "                    node = next\n",
    "                    \n",
    "                else:\n",
    "                    \n",
    "                    return []"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Voltar ao topo](#Árvore-Patrícia)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Na prática"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Exemplo"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Realizaremos o mesmo exemplo exposto anteriormente, só que na prática."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'casco$'"
      ]
     },
     "execution_count": 43,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tree = Arvore(\"casco\")\n",
    "tree.raiz"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ao visualizar a raíz, notamos a presença de uma string. Isso quer dizer que estamos em um nó folha, fato este representado pelo $\\$$ que finaliza a palavra."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "str"
      ]
     },
     "execution_count": 46,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "type(tree.raiz)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Naturalmente, pelo fato desta árvore conter apenas uma palavra, não há uso de objetos `Node`, tampouco há a presença de filhos:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Não há filhos!\n"
     ]
    }
   ],
   "source": [
    "try:\n",
    "    tree.raiz.filhos\n",
    "except AttributeError:\n",
    "    print(\"Não há filhos!\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# tree.raiz.filhos"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A inserção de mais uma palavra fará com que o objeto `str` seja substituído por um `Node`, e que a profundidade da árvore aumente."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[4|a]"
      ]
     },
     "execution_count": 49,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tree.insere(\"cascalho\")\n",
    "tree.raiz"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['cascalho$', 'casco$']"
      ]
     },
     "execution_count": 50,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tree.raiz.filhos"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Sigamos adiante com a adição das demais palavras:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {},
   "outputs": [],
   "source": [
    "tree.insere(\"cascata\")\n",
    "tree.insere(\"dama\")\n",
    "tree.insere(\"domando\")\n",
    "tree.insere(\"dominar\")\n",
    "tree.insere(\"domínio\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Vejamos como a árvore está em relação à imagem vista anteriormente, replicada abaixo por conveniência:\n",
    "\n",
    "![](imagens/exemplo_de_patricia.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Profundidade 0:**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0|c]"
      ]
     },
     "execution_count": 52,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tree.raiz"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Profundidade 1:**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[4|a], [1|a]]"
      ]
     },
     "execution_count": 53,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tree.raiz.filhos"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Profundidade 2:**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[5|l], 'casco$', 'dama$', [3|a]]"
      ]
     },
     "execution_count": 54,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(tree.raiz.filhos[0].filhos + \n",
    " tree.raiz.filhos[1].filhos)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Para efeito ilustrativo, adicionaremos a partir daqui espaços vazios quando houver folhas (objetos `Node` sem filho)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Profundidade 3:**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['cascalho$', 'cascata$', '', '', '', '', 'domando$', [3|i]]"
      ]
     },
     "execution_count": 55,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(tree.raiz.filhos[0].filhos[0].filhos + \n",
    " [\"\"] +\n",
    " [\"\"] +\n",
    " [\"\"] +\n",
    " [\"\"] +\n",
    " tree.raiz.filhos[1].filhos[1].filhos)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Profundidade 4:**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['',\n",
       " '',\n",
       " '',\n",
       " '',\n",
       " '',\n",
       " '',\n",
       " '',\n",
       " '',\n",
       " '',\n",
       " '',\n",
       " '',\n",
       " '',\n",
       " '',\n",
       " '',\n",
       " 'dominar$',\n",
       " 'domínio$']"
      ]
     },
     "execution_count": 56,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "([\"\"] +\n",
    " [\"\"] +\n",
    " [\"\"] +\n",
    " [\"\"] +\n",
    " [\"\"] +\n",
    " [\"\"] +\n",
    " [\"\"] +\n",
    " [\"\"] +\n",
    " [\"\"] +\n",
    " [\"\"] +\n",
    " [\"\"] +\n",
    " [\"\"] +\n",
    " [\"\"] +\n",
    " [\"\"] +\n",
    " tree.raiz.filhos[1].filhos[1].filhos[1].filhos)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Voltar ao topo](#Árvore-Patrícia)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Teste de confiabilidade"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A fim de garantir a confiabilidade da estrutura de dados, fizemos um teste intensivo de inserção de palavras, valendo-nos do dicionário em português do Brasil fornecido pelo LibreOffice."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 76,
   "metadata": {},
   "outputs": [],
   "source": [
    "from random import shuffle"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 77,
   "metadata": {},
   "outputs": [],
   "source": [
    "def load_dict(path):\n",
    "    with open(path, \"r\", encoding=\"utf-8\") as file:\n",
    "        return [line.strip(\"\\n\") for line in file.readlines()]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Carreguemos o dicionário:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 78,
   "metadata": {},
   "outputs": [],
   "source": [
    "pt_br = load_dict(\"./dictionaries/palavras.txt\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 96,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "O dicionário possui 320139 palavras.\n"
     ]
    }
   ],
   "source": [
    "print(f\"O dicionário possui {len(pt_br)} palavras.\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "O teste consiste na inserção, verificação e remoção de palavras de forma aleatória. Dessa forma, precisamos de três cópias do dicionário:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 79,
   "metadata": {},
   "outputs": [],
   "source": [
    "load   = pt_br.copy()\n",
    "check  = pt_br.copy()\n",
    "remove = pt_br.copy()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 80,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "load[:5]:   ['a', 'ª', 'à', 'á', 'ã']\n",
      "check[:5]:  ['a', 'ª', 'à', 'á', 'ã']\n",
      "remove[:5]: ['a', 'ª', 'à', 'á', 'ã']\n"
     ]
    }
   ],
   "source": [
    "print(f\"load[:5]:   {load[:5]}\")\n",
    "print(f\"check[:5]:  {check[:5]}\")\n",
    "print(f\"remove[:5]: {remove[:5]}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Vamos utilizar a função `shuffle`, do módulo `random`, para obter versões aleatorizadas do dicionário:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 90,
   "metadata": {},
   "outputs": [],
   "source": [
    "shuffle(load)\n",
    "shuffle(check)\n",
    "shuffle(remove)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 91,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "load[:5]:   ['diftógrafo', 'cientifização', 'manolita', 'xantematina', 'ácoros-bastardos']\n",
      "check[:5]:  ['pau-morcego', 'executado', 'catartínico', 'coptotermes', 'alveoliforme']\n",
      "remove[:5]: ['circungirar', 'colossigmoidostômico', 'francoáceo', 'ofiuroideo', 'asquistítico']\n"
     ]
    }
   ],
   "source": [
    "print(f\"load[:5]:   {load[:5]}\")\n",
    "print(f\"check[:5]:  {check[:5]}\")\n",
    "print(f\"remove[:5]: {remove[:5]}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Por fim, seguiremos adiante com o teste propriamente dito. Basicamente, a expectativa é que a primeira palavra inserida seja a primeira da lista `load` e termine com a primeira palavra de `remove`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 92,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'diftógrafo$'"
      ]
     },
     "execution_count": 92,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tree = Arvore(load[0])\n",
    "tree.raiz"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 93,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Inserindo...\n",
      "Verificando...\n",
      "Removendo...\n",
      "Sucesso.\n"
     ]
    }
   ],
   "source": [
    "print(\"Inserindo...\")\n",
    "\n",
    "for word in load[1:]:\n",
    "    # print(f\"Inserting {word}...\")\n",
    "    tree.insere(word)\n",
    "    if not tree.check(word):\n",
    "        raise ValueError(f\"Não pude encontrar a palavra {word}!\")\n",
    "\n",
    "print(\"Verificando...\")\n",
    "\n",
    "for word in check:\n",
    "    # print(f\"Verifying {word}...\")\n",
    "    if not tree.check(word):\n",
    "        raise ValueError(f\"Não pude verificar que a palavra {word} está mesmo na árvore!\")\n",
    "\n",
    "print(\"Removendo...\")\n",
    "\n",
    "for word in remove[1:]:\n",
    "    # print(f\"Removing {word}...\")\n",
    "    tree.remove(word)\n",
    "    if tree.check(word):\n",
    "        raise ValueError(f\"Não consegui remover a palavra {word}!\")\n",
    "\n",
    "print(\"Sucesso.\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 95,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'circungirar$'"
      ]
     },
     "execution_count": 95,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tree.raiz"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Voltar ao topo](#Árvore-Patrícia)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Complexidade das operações"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- **Busca:** $O(|chave|)$;\n",
    "- **Inserção:** $O(|chave| + |X|)$;\n",
    "- **Remoção:** $O(|chave| + |X|)$;\n",
    "- **Listagem de todos os registros que contêm determinado prefixo:** $O(|s| + k)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Voltar ao topo](#Árvore-Patrícia)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Comparação com outras estruturas de dados"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- Compacta em relação a Trie;\n",
    "- Problema de caminhos de uma única direção resolvido;\n",
    "- Evita o problema de desperdício de memória nos nós internos da Trie (cada nó da árvore PATRICIA contém a posição da chave que deve ser comparada e o dígito a ser usado nessa comparação). "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Voltar ao topo](#Árvore-Patrícia)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Aplicações"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- Armazenamento de dados no Ethereum;\n",
    "- Bloqueio de IPs pelo Sqreen;\n",
    "- Indexação de arquivos XML."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Voltar ao topo](#Árvore-Patrícia)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Fim. Obrigado pela atenção :)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Perguntas?**"
   ]
  }
 ],
 "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.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}