Estrutura de Dados - Pesquisa Digital

Tipo de documento:Produção de Conteúdo

Área de estudo:Lingua Portuguesa

Documento 1

IMG4 – Árvore Trie. IMG5 – Trie Binaria. IMG6 – Inserir Trie. IMG7 – Inserir Trie. IMG8 – Busca Trie. IMG19 – Remove Patricia. LISTA DE ABREVIATURAS TRIE Vem da palavra “Retrieval” que quer dizer “Recuperação” BITS Quer dizer “Binary Digit” que quer dizer “Dígito Binário” PATRICIA Significa “Practical Algorithm To Retrieve Information Coded In Alphanumeric” que quer dizer “Algoritmo Prático para Recuperar Informação Codificada em Alfanumérico” INTERNET é redução do termo "internetwork", que significa duas ou mais redes de computadores distintas conectadas WEB Palavra inglesa que significa teia ou rede, no caso deste trabalho significa rede de computadores conectados via internet SUMÁRIO 1 PESQUISA DIGITAL. O que são Árvores. O que são Árvores de pesquisa. ÁRVORES DIGITAIS. Características (Patricia). Forma de Inserção (Patricia). Forma de Busca (Patricia).

Forma de Remoção (Patricia). Aplicabilidade da Árvore Patricia. A medida a quantidade de dados armazenados em determinados bancos de dados ou servidores foram crescendo as empresas começaram a adotar medidas para melhorar a forma de pesquisa e garantir que determinados dados fossem encontrados mais facilmente. E para o meio digital a busca digital veio sendo inovação! Mas como é realizada esta forma de pesquisa? Como então que esta pesquisa traz benefícios? Existe alguma desvantagem ao usá-la? É uma pesquisa que está em alta? Na parte de desenvolvimento será explicado com mais clareza alguns métodos de pesquisa e a sua importância, juntamente com suas funcionalidades! Mas de início é necessário entender 6 que esse modo de pesquisa necessita de alguns detalhes importantes para o seu funcionamento, sendo um deles o conceito de “Árvore”.

O que são Árvores O que realmente se imagina quando se escuta a palavra “árvore”? Não é necessário pensar muito para entender que é uma estrutura feita por raízes, caule, galhos e folhas! Dessa forma também se aplica o conceito para entender a estrutura que uma árvore terá em uma implementação digital. As árvores no meio tecnológico são compostas por raiz (também conhecido como o ‘Pai’ da árvore), galhos (que seria as ligações entre um nó e outro), folhas (que são os filhos de cada raiz ou de cada nó) e subárvores (nada mais do que filhos que também tem filhos) – lembrando que o conjunto de uma raiz com um ou mais filhos é denominado “nó”. Cada árvore completa tem basicamente este conjunto supracitado e age como um auxiliar importante para meios de pesquisa no âmbito da tecnologia da informação.

ufrj. br/adriano/c/apostila/arvore. htm#arvconj Existe árvores que são binárias – árvores que somente detém de dois filhos em cada nó, como o exemplo citado acima - e as árvores que não são binárias – também chamadas de árvores genéricas, pois podem conter infinitos filhos para cada nó ou para cada Raiz. Nesse trabalho será abordado um pouco da aplicabilidade dos dois tipos de árvores para a realização da pesquisa digital. O que são Árvores de pesquisa Os estudiosos da área da informática decidiram, a partir dos conceitos citados no tópico anterior sobre árvores, montar uma forma pesquisa que fosse inovador e que dinamizasse o tempo que era gasto para armazenar ou pesquisar certos dados em um servidor, por exemplo.

Ambas estruturas foram criadas para realizar pesquisas, mas a Patricia é uma atualização da Trie, melhorando certos pontos de defeito encontrado na primeira estrutura. Repare a seguir a especificada e característica de cada árvore. Árvores Tries “Árvore Trie” é uma árvore de pesquisa utilizada principalmente quando as chaves são de tamanho variável. É uma estrutura dada em m-vias na qual as ramificações em qualquer nível são dadas por apenas uma parte da chave dada pelo usuário e não pela chave inteira. Assim a chave informada é distribuída por entre os nós até terminar o conteúdo da chave. Agora na árvore trie o usuário vai informar cada nome de rua até chegar 10 naquela casa em questão. Nesse caso o usuário pode informar uma um caminho incompleto, sendo que nesse caso o sistema irá retornar para o usuário todas as casas encontradas nesse endereço incompleto.

Basicamente o sistema não sai à procura de uma chave igual à que o usuário digitou, e sim, o sistema sai entrando na árvore através de cada termo digitado pelo usuário. Repare a imagem a seguir e perceba que na árvore trie o processo é feito diferente: a partir do caminho que se tem é que será gerado o resultado adequado. IMG4 – Árvore trie: http://dcm. Para percorrer é necessário acompanhar a sequência de bits da chave digitada, no caso para o tipo de árvore trie binária. IMG5 – Trie Binária: https://www. passeidireto. com/arquivo/1009631/25-pesquisa-digital 2. Forma de Inserção (Trie) Para realizar a inserção na árvore trie o sistema começa realizando uma pesquisa em todo o conjunto usando a chave que que será inserida pelo usuário – lembrando que, como já foi dito antes, a pesquisa é realizada termo a termo e cada caractere da chave corresponde a uma raiz.

pdf Na imagem acima o Sistema não encontrou a chave “amy” na árvore e assim fez a inserção termo a termo inserindo cada caractere em uma raiz da árvore. Agora segue a próxima imagem e perceba que, no momento de inserir a chave “ann” o sistema encontra o primeiro caractere na árvore (o caractere “a”), logo o sistema permaneceu com esse caractere e puxou um filho para ele, construindo uma nova sequência na árvore. IMG7 – Inserir Trie: http://www. ufjf. br/jairo_souza/files/2009/12/6-Strings-Pesquisa-Digital. dcc. ufmg. br/~cunha/teaching/20121/aeds2/radixsearch. pdf 2. Forma de Remoção (Trie) A forma de remoção não é complicada para entender! Nas árvores tries o sistema, a partir da chave digitada, identifica onde (em que nó, raiz) está localizado aquele dado.

Aplicabilidade da Árvore Trie Existe várias aplicabilidades para a árvore trie, mas por ser um código que gasta bastante memória muitos não optam por utilizar esse método. Mais à frente será adicionado em pauta as vantagens e desvantagens a cerca desse tema e assim poderá perceber que por mais que haja aplicabilidade real, mas o sistema cobra um pouco mais do hardware do que o de costume. Para esse método os sistemas aplicam bastante para buscas relacionadas a dicionários digitais, em que o usuário insere as letras iniciais da palavra que deseja ou até mesmo todas as letras da palavra a fim de encontrar a palavra que realmente deseja no dicionário online. Outra forma de aplicar é em grandes textos que tenha dimensões imensas, também auxilia para a procura de palavras nos textos (Ao inserir determinada palavra o sistema começa uma busca pelas palavras existentes no texto).

Isso pode ser comparado à forma de pesquisa que o próprio google apresenta: ao pressionar “F3” ou “Alt+F” no navegador ele vai 16 apresentar caixa para pesquisa de palavras na página. Assim criaram o método que chamaram de patricia, reduzindo consideravelmente o consumo de memória, a extensão da árvore de pesquisa e aumentando a velocidade de pesquisa. Criado por Morrison em 1968, estendido por Knuth em 1973, Sedgewick em 1988, Gonnet e Baeza-Yates em 1991, “Patricia” é uma abreviação para “Practical Algorithm To Retrieve Information Coded In Alphanumeric” que, em português, significa “Algoritmo Prático para Recuperar Informação Codificada em Alfanumérico”. Essa árvore é usada para pesquisas que contem, como chave, os números binários (0 ou 1) – se tentar usar o algoritmo patricia em outras formas de chave, não conseguirá gerenciar da forma ideal.

Comparativo: Árvore Patricia e Árvore Trie Um grande problema existente nas árvores tries e que resulta perca de memória exponencialmente nos sistemas é o inconveniente transtorno com caminhos de uma só direção ou, na linguagem das árvores binárias, raízes que tem somente um filho ao invés de dois filhos completos. Sendo assim, na criação das árvores patricias, os pesquisadores eliminaram esse problema de uma maneira elegante e simples: cada nó raiz da árvore contém o índice do caractere a ser testado para decidir qual subárvores seguir. Forma de Inserção (Patricia) Para realizar a inserção o sistema faz algumas operações um tanto complicadas, mas se seguir algumas imagens perceberá que não é um “bicho de 7 cabeças”. Assim para facilitar melhor o entendimento siga as imagens e as descrições abaixo: 19 Para inserir um determinado dado em uma árvore patricia vazia o sistema somente insere o dado na própria raiz, pois não há comparações a se fazer e nenhum nó para ser alterado: IMG13 – Inserir Patricia: http://dcm.

ffclrp. usp. br/~augusto/teaching/aedii/AED-II-Pesquisa-Digital. Logo se esse índice diferencia o “B” do “H” o sistema terá que substituir o valor “B” pelo número do índice que está sendo diferenciado – no caso o 3 – e analisar esse 20 terceiro índice na chave “B” e na chave “H”: o que tiver a chave 1 irá para a direita desse nó em que está o número 3, o que tiver a chave 0 terá que ir para o lado esquerdo: IMG15 – Inserir Patricia: http://dcm. ffclrp. usp. br/~augusto/teaching/aedii/AED-II-Pesquisa-Digital. pdf Agora o processo de inserção se repete para todos os demais itens a ser inseridos na árvore, assim, se os passos acima forem feitos corretamente até a última chave o sistema apresentará a seguinte árvore: IMG16 – Inserir Patricia: http://dcm. pdf Siga a imagem acima e suponha que o usuário quer encontrar, por exemplo, a chave [001001].

Nesse caso o sistema iria dividir a chave informada pelo usuário e analisar o primeiro termo (perceba que na raiz principal está o número 1, assim quer dizer que o sistema precisa analisar o primeiro termo da chave informada), caso esse termo seja 0 o sistema passa para a raiz da esquerda, caso seja 1 o sistema passa para a direita. Nesse caso o primeiro termo da chave é 0, então o sistema passa para a parte esquerda. Perceba agora que nessa parte a raiz está com o valor 3, isso indica que o sistema precisa analisar o terceiro valor da chave para realizar a pesquisa. Caso a terceira chave seja 0 vai para a esquerda, caso seja 1 vai para direita. ffclrp. usp. br/~augusto/teaching/aedii/AED-II-Pesquisa-Digital. pdf Assim o sistema irá seguir removendo até que todos os nós da árvore sejam removidos.

A característica para remoção segue a mesma ideia para todos os nós da árvore. São usadas pois o sistema de comparações são feitas com a chave inteira, comparando se essa chave existe ou não: se existir retorna uma confirmação de existência e se não existir retorna mensagens ou algo que indique que aquele valor não está arquivado. Mas comparando às pesquisas digitais essas formas de busca não são muito bem eficientes e por isso veio a criação dos tipos de pesquisa trie e patricia. Tais formas de busca evoluíram a forma de lidar com os dados, pois a partir desses métodos os usuários podem buscar por seus dados sem precisar saber o dado completo, ou seja, pode pesquisar por um nome sem saber ao certo o nome completo da pessoa.

Sendo assim com poucos caracteres pode ser realizado um filtro semelhante aos existentes nos campos de pesquisa na web. Tais pesquisas são semelhantes às buscas realizadas em um dicionário. FRANCISCO, Jairo. Busca Digital: Trie e Árvore Patrícia. Disponível em: <http://www. ufjf. br/jairo_souza/files/2009/12/6-Strings-Pesquisa-Digital. GPEC. Busca Digital. Disponível em: <http://www. gpec. ucdb. Acesso em: 23 jun. CUNHA, Ítalo. Pesquisa Digital: Algoritmos e Estruturas de Dados II. Disponível em: <http://homepages. dcc. pdf>. Acesso em: 23 jun.

534 R$ para obter acesso e baixar trabalho pronto

Apenas no StudyBank

Modelo original

Para download