bk-tree-modification


Namebk-tree-modification JSON
Version 0.1 PyPI version JSON
download
home_pageNone
SummaryA simple BK-Tree implementation for finding similar words
upload_time2024-06-15 22:37:52
maintainerNone
docs_urlNone
authorKaren Arcoverde
requires_pythonNone
licenseNone
keywords bktree edit distance similarity
VCS
bugtrack_url
requirements No requirements were recorded.
Travis-CI No Travis.
coveralls test coverage No coveralls.
            # topicos-especiais-sd
## Correção Ortográfica Automática de Palavras Baseada em Dicionário

Foi feito um estudo dos possíveis algoritmos que poderiam ser implementados para este projeto. Por conseguinte, foi escolhido o melhor algoritmo para implementação.

### Distância de Levenshtein

A **distância de Levenshtein** é a parte principal desse projeto, pois todos os algoritmos usados derivam-se dele. É possível perceber que ela foi utilizada em quase todos os algoritmos pesquisados. Ela mede o número mínimo de edições necessárias para transformar uma string em outra. Estas edições incluem inserções, deleções e substituições de caracteres.

### BK-Tree

A BK-Tree consiste em botar as palavras em uma árvore com pesos (distância de Levenshtein) e pecorrer a árvore pegando todas as distâncias menores ou iguais a distância limite estipulada. 

Para descobrir a distância entre duas palavras, é criada a matriz dp. A matriz dp[m][n] representa a distância total (Levenshtein) entre duas strings(a e b). A matriz dp tem dimensões (m+1)x(n+1), sendo m o comprimento da string a e n o comprimento da string b. Cada célula dp[i][j] armazena a distância de edição mínima entre as substrings a[0:i] e b[0:j]. A matriz é inicializada com dp[i][0] = i e dp[0][j] = j, indicando as transformações para strings vazias. O preechimento da matriz começa no dp[1][1] até dp[m][n], para cada célula dp[i][j], os caracteres da string a[i-1] e b[j-1] são comparados. Para o caso de serem iguais, dp[i-1][j-1] é transferido diretamente para dp[i][j], o que significa que não precisa ter nenhuma edição. Se forem diferentes, a célula é preenchida com o mínimo entre as possíveis operações(inserção, deleção e substituição).

Depois para buscar palavras semelhantes na árvore, é verificado a distância de edição entre o nó root e a palavra, caso ela seja menor que a variável "TOL" (tolerância), a palavra do root é adicionada a lista de resultados. Após essa verificação, é analisada os nós filhos de root investigando quais palavras tem as distâncias dentro do intervalo [distância - TOL, distância + TOL] para adicionar na lista de resultados.

Para adicionar a palavra na árvore, temos algumas etapas:
1. Se o nó root está vazio, a palavra atual (curr) que está sendo lida é colocada nesse nó.
2. Se já existe a palavra no root, é calculada a distância entre o root e a palavra (curr) que precisamos adicionar.
3. Se não possuir nó para essa distância na árvore no vetor next, cria-se um novo espaço para essa palavra (curr), atualizando o vetor next para apontar para ela e incrementando o contador ptr.
4. Se ja existir um nó para essa distância, não é criado um novo espaço, adiciona a palavra (curr) nesse nó existente. 



### FuzzyWuzzy


### Fórmula de Cálculo da Similaridade

A similaridade entre duas strings é calculada usando a seguinte fórmula:

```plaintext
Similaridade = (1 - (Distância de Levenshtein / Comprimento máximo das duas strings)) * 100
```
Esta fórmula fornece um valor percentual que reflete quão semelhantes são as duas strings baseado na distância de Levenshtein, onde 100% representa uma correspondência perfeita e 0% indica nenhuma similaridade.

### Referências
http://blog.notdot.net/2007/4/Damn-Cool-Algorithms-Part-1-BK-Trees \
https://www.youtube.com/watch?v=oIsPB2pqq_8 \
https://medium.com/datenworks/fuzzy-search-buscando-texto-por-aproxima%C3%A7%C3%A3o-6c7214e0ea01



            

Raw data

            {
    "_id": null,
    "home_page": null,
    "name": "bk-tree-modification",
    "maintainer": null,
    "docs_url": null,
    "requires_python": null,
    "maintainer_email": null,
    "keywords": "bktree edit distance similarity",
    "author": "Karen Arcoverde",
    "author_email": "arcoverdek@gmail.com",
    "download_url": "https://files.pythonhosted.org/packages/e3/46/f60208e01ab6fc33051deca4e83c0f28aa96624486bfb851d90a160629fa/bk_tree_modification-0.1.tar.gz",
    "platform": null,
    "description": "# topicos-especiais-sd\r\n## Corre\u00c3\u00a7\u00c3\u00a3o Ortogr\u00c3\u00a1fica Autom\u00c3\u00a1tica de Palavras Baseada em Dicion\u00c3\u00a1rio\r\n\r\nFoi feito um estudo dos poss\u00c3\u00adveis algoritmos que poderiam ser implementados para este projeto. Por conseguinte, foi escolhido o melhor algoritmo para implementa\u00c3\u00a7\u00c3\u00a3o.\r\n\r\n### Dist\u00c3\u00a2ncia de Levenshtein\r\n\r\nA **dist\u00c3\u00a2ncia de Levenshtein** \u00c3\u00a9 a parte principal desse projeto, pois todos os algoritmos usados derivam-se dele. \u00c3\u2030 poss\u00c3\u00advel perceber que ela foi utilizada em quase todos os algoritmos pesquisados. Ela mede o n\u00c3\u00bamero m\u00c3\u00adnimo de edi\u00c3\u00a7\u00c3\u00b5es necess\u00c3\u00a1rias para transformar uma string em outra. Estas edi\u00c3\u00a7\u00c3\u00b5es incluem inser\u00c3\u00a7\u00c3\u00b5es, dele\u00c3\u00a7\u00c3\u00b5es e substitui\u00c3\u00a7\u00c3\u00b5es de caracteres.\r\n\r\n### BK-Tree\r\n\r\nA BK-Tree consiste em botar as palavras em uma \u00c3\u00a1rvore com pesos (dist\u00c3\u00a2ncia de Levenshtein) e pecorrer a \u00c3\u00a1rvore pegando todas as dist\u00c3\u00a2ncias menores ou iguais a dist\u00c3\u00a2ncia limite estipulada. \r\n\r\nPara descobrir a dist\u00c3\u00a2ncia entre duas palavras, \u00c3\u00a9 criada a matriz dp. A matriz dp[m][n] representa a dist\u00c3\u00a2ncia total (Levenshtein) entre duas strings(a e b). A matriz dp tem dimens\u00c3\u00b5es (m+1)x(n+1), sendo m o comprimento da string a e n o comprimento da string b. Cada c\u00c3\u00a9lula dp[i][j] armazena a dist\u00c3\u00a2ncia de edi\u00c3\u00a7\u00c3\u00a3o m\u00c3\u00adnima entre as substrings a[0:i] e b[0:j]. A matriz \u00c3\u00a9 inicializada com dp[i][0] = i e dp[0][j] = j, indicando as transforma\u00c3\u00a7\u00c3\u00b5es para strings vazias. O preechimento da matriz come\u00c3\u00a7a no dp[1][1] at\u00c3\u00a9 dp[m][n], para cada c\u00c3\u00a9lula dp[i][j], os caracteres da string a[i-1] e b[j-1] s\u00c3\u00a3o comparados. Para o caso de serem iguais, dp[i-1][j-1] \u00c3\u00a9 transferido diretamente para dp[i][j], o que significa que n\u00c3\u00a3o precisa ter nenhuma edi\u00c3\u00a7\u00c3\u00a3o. Se forem diferentes, a c\u00c3\u00a9lula \u00c3\u00a9 preenchida com o m\u00c3\u00adnimo entre as poss\u00c3\u00adveis opera\u00c3\u00a7\u00c3\u00b5es(inser\u00c3\u00a7\u00c3\u00a3o, dele\u00c3\u00a7\u00c3\u00a3o e substitui\u00c3\u00a7\u00c3\u00a3o).\r\n\r\nDepois para buscar palavras semelhantes na \u00c3\u00a1rvore, \u00c3\u00a9 verificado a dist\u00c3\u00a2ncia de edi\u00c3\u00a7\u00c3\u00a3o entre o n\u00c3\u00b3 root e a palavra, caso ela seja menor que a vari\u00c3\u00a1vel \"TOL\" (toler\u00c3\u00a2ncia), a palavra do root \u00c3\u00a9 adicionada a lista de resultados. Ap\u00c3\u00b3s essa verifica\u00c3\u00a7\u00c3\u00a3o, \u00c3\u00a9 analisada os n\u00c3\u00b3s filhos de root investigando quais palavras tem as dist\u00c3\u00a2ncias dentro do intervalo [dist\u00c3\u00a2ncia - TOL, dist\u00c3\u00a2ncia + TOL] para adicionar na lista de resultados.\r\n\r\nPara adicionar a palavra na \u00c3\u00a1rvore, temos algumas etapas:\r\n1. Se o n\u00c3\u00b3 root est\u00c3\u00a1 vazio, a palavra atual (curr) que est\u00c3\u00a1 sendo lida \u00c3\u00a9 colocada nesse n\u00c3\u00b3.\r\n2. Se j\u00c3\u00a1 existe a palavra no root, \u00c3\u00a9 calculada a dist\u00c3\u00a2ncia entre o root e a palavra (curr) que precisamos adicionar.\r\n3. Se n\u00c3\u00a3o possuir n\u00c3\u00b3 para essa dist\u00c3\u00a2ncia na \u00c3\u00a1rvore no vetor next, cria-se um novo espa\u00c3\u00a7o para essa palavra (curr), atualizando o vetor next para apontar para ela e incrementando o contador ptr.\r\n4. Se ja existir um n\u00c3\u00b3 para essa dist\u00c3\u00a2ncia, n\u00c3\u00a3o \u00c3\u00a9 criado um novo espa\u00c3\u00a7o, adiciona a palavra (curr) nesse n\u00c3\u00b3 existente. \r\n\r\n\r\n\r\n### FuzzyWuzzy\r\n\r\n\r\n### F\u00c3\u00b3rmula de C\u00c3\u00a1lculo da Similaridade\r\n\r\nA similaridade entre duas strings \u00c3\u00a9 calculada usando a seguinte f\u00c3\u00b3rmula:\r\n\r\n```plaintext\r\nSimilaridade = (1 - (Dist\u00c3\u00a2ncia de Levenshtein / Comprimento m\u00c3\u00a1ximo das duas strings)) * 100\r\n```\r\nEsta f\u00c3\u00b3rmula fornece um valor percentual que reflete qu\u00c3\u00a3o semelhantes s\u00c3\u00a3o as duas strings baseado na dist\u00c3\u00a2ncia de Levenshtein, onde 100% representa uma correspond\u00c3\u00aancia perfeita e 0% indica nenhuma similaridade.\r\n\r\n### Refer\u00c3\u00aancias\r\nhttp://blog.notdot.net/2007/4/Damn-Cool-Algorithms-Part-1-BK-Trees \\\r\nhttps://www.youtube.com/watch?v=oIsPB2pqq_8 \\\r\nhttps://medium.com/datenworks/fuzzy-search-buscando-texto-por-aproxima%C3%A7%C3%A3o-6c7214e0ea01\r\n\r\n\r\n",
    "bugtrack_url": null,
    "license": null,
    "summary": "A simple BK-Tree implementation for finding similar words",
    "version": "0.1",
    "project_urls": null,
    "split_keywords": [
        "bktree",
        "edit",
        "distance",
        "similarity"
    ],
    "urls": [
        {
            "comment_text": "",
            "digests": {
                "blake2b_256": "892cf4a3d80700862baa29f1b501af768ad8fdf099aeb4d69eafc15b91982b5d",
                "md5": "91ede362f02f3d14e62193c5e85312c3",
                "sha256": "ece53700dd6f20b4f3b867b037fb9094c0f730101981346cdfb0351224bb4f1b"
            },
            "downloads": -1,
            "filename": "bk_tree_modification-0.1-py3-none-any.whl",
            "has_sig": false,
            "md5_digest": "91ede362f02f3d14e62193c5e85312c3",
            "packagetype": "bdist_wheel",
            "python_version": "py3",
            "requires_python": null,
            "size": 4189,
            "upload_time": "2024-06-15T22:37:50",
            "upload_time_iso_8601": "2024-06-15T22:37:50.742153Z",
            "url": "https://files.pythonhosted.org/packages/89/2c/f4a3d80700862baa29f1b501af768ad8fdf099aeb4d69eafc15b91982b5d/bk_tree_modification-0.1-py3-none-any.whl",
            "yanked": false,
            "yanked_reason": null
        },
        {
            "comment_text": "",
            "digests": {
                "blake2b_256": "e346f60208e01ab6fc33051deca4e83c0f28aa96624486bfb851d90a160629fa",
                "md5": "cdf98756e6e9355a15a5bba5413755eb",
                "sha256": "367deab5ca7af56e3f91866e53ba38fa7bf6b47922a319af230b63114749ed9e"
            },
            "downloads": -1,
            "filename": "bk_tree_modification-0.1.tar.gz",
            "has_sig": false,
            "md5_digest": "cdf98756e6e9355a15a5bba5413755eb",
            "packagetype": "sdist",
            "python_version": "source",
            "requires_python": null,
            "size": 4380,
            "upload_time": "2024-06-15T22:37:52",
            "upload_time_iso_8601": "2024-06-15T22:37:52.471906Z",
            "url": "https://files.pythonhosted.org/packages/e3/46/f60208e01ab6fc33051deca4e83c0f28aa96624486bfb851d90a160629fa/bk_tree_modification-0.1.tar.gz",
            "yanked": false,
            "yanked_reason": null
        }
    ],
    "upload_time": "2024-06-15 22:37:52",
    "github": false,
    "gitlab": false,
    "bitbucket": false,
    "codeberg": false,
    "lcname": "bk-tree-modification"
}
        
Elapsed time: 0.32046s