# 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"
}
JSON