SymSpell
v6.7.2
Исправление орфографии и нечеткий поиск: в 1 миллион раз быстрее с помощью симметричного алгоритма коррекции орфографии удалить
Симметричный алгоритм коррекции орфографии удаляет сложность редактирования генерации кандидатов и поиска словаря для данного расстояния Дамерау-Левенштейна. Это на шесть порядков быстрее (чем стандартный подход с удалениями + транспони + заменяет + вставки) и независимым от языка.
В противоположность другим алгоритмам требуются только удаления, не требуют транспозирования + заменяют + вставки. Транспозы + заменяют + вставки входного термина преобразуются в удаления словаря. Заменяет и вставки являются дорогими и зависимыми от языка: например, в Китае 70 000 персонажей Unicode Han!
Скорость поступает из недорогой генерации кандидатов только для удаления и предварительной разчисления .
Среднее 5 -буквенное слово имеет около 3 миллионов возможных ошибок орфографии в пределах максимальной редактирования 3,
Но Sympell должен генерировать только 25 удалений, чтобы покрыть их все, как при предварительном рассмотрении, так и во время поиска. Магия!
Если вам нравится Symspell, попробуйте SeekStorm -библиотека полной текстовой библиотеки и многопользовательского поиска в Rust (Open Source).
Copyright (c) 2022 Wolf Garbe
Version: 6.7.2
Author: Wolf Garbe <[email protected]>
Maintainer: Wolf Garbe <[email protected]>
URL: https://github.com/wolfgarbe/symspell
Description: https://seekstorm.com/blog/1000x-spelling-correction/
MIT License
Copyright (c) 2022 Wolf Garbe
Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated
documentation files (the "Software"), to deal in the Software without restriction, including without limitation
the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software,
and to permit persons to whom the Software is furnished to do so, subject to the following conditions:
The above copyright notice and this permission notice shall be included in all
copies or substantial portions of the Software.
https://opensource.org/licenses/MIT
Lookup обеспечивает очень быструю коррекцию орфографии отдельных слов.
0,033 миллисекунд/слово (редактирование расстояния 2) и 0,180 миллисекунд/слово (редактирование расстояния 3) (одно ядро на MacBook Pro 2012 года)
В 1 870 раза быстрее, чем BK-Tree (см. Bender 1: Размер словаря = 500 000, максимальное расстояние редактирования = 3, члены запроса со случайным расстоянием редактирования = 0 ... Максимальное расстояние редактирования, словес = 0)
В 1 миллион раз быстрее, чем алгоритм Норвига (см. Бандкарт 2: размер словаря = 29 157, максимальное расстояние редактирования = 3, члены запроса с фиксированным расстоянием редактирования = максимальное расстояние редактирования, вербоза = 0)
В 1000 раз быстрее алгоритм коррекции орфографии
Быстрое приблизительное сопоставление строк с большими расстояниями редактирования в больших данных
Очень быстрая очистка данных названий продуктов, названий компаний и названий улиц
Sub-Millisecond составное соединение автоматическое исправление орфографии
Symspell vs. Bk-Tree: в 100x более простых поиска строк и проверка орфографии
Быстрая сегментация слова для шумного текста
Обрезка Radix Trie - Radix Trie на стероидах
LookupCompound поддерживает автоматическую коррекцию орфографии составных строк ввода .
1. Составной расщепление и разместите
Lookup () предполагает каждую входную строку в качестве одного термина . LookupCompound также поддерживает составное разделение / разложение с тремя случаями:
Расщепление ошибок, ошибок конкатенации, ошибок замены, ошибок транспозиции, ошибок делеции и ошибок вставки могут смешать в одном и том же словом.
2. Автоматическая коррекция орфографии
Примеры:
- whereis th elove hehad dated forImuch of thepast who couqdn'tread in sixthgrade and ins pired him
+ where is the love he had dated for much of the past who couldn't read in sixth grade and inspired him (9 edits)
- in te dhird qarter oflast jear he hadlearned ofca sekretplan
+ in the third quarter of last year he had learned of a secret plan (9 edits)
- the bigjest playrs in te strogsommer film slatew ith plety of funn
+ the biggest players in the strong summer film slate with plenty of fun (9 edits)
- Can yu readthis messa ge despite thehorible sppelingmsitakes
+ can you read this message despite the horrible spelling mistakes (9 edits) 0,2 миллисекунд / слово (редактирование расстояния 2) 5000 слов / второе (одно ядро на MacBook Pro 2012 года)
WordSegmation делит строку на слова, вставляя недостающие пространства в соответствующих положениях.
Примеры:
- thequickbrownfoxjumpsoverthelazydog
+ the quick brown fox jumps over the lazy dog
- itwasabrightcolddayinaprilandtheclockswerestrikingthirteen
+ it was a bright cold day in april and the clocks were striking thirteen
- itwasthebestoftimesitwastheworstoftimesitwastheageofwisdomitwastheageoffoolishness
+ it was the best of times it was the worst of times it was the age of wisdom it was the age of foolishness Приложения:
Производительность:
4 миллисекунд для сегментирования строки 185 чар на 53 слова (одно ядро на MacBook Pro 2012 года)
Одиночное слово + enter: отображать предложения по орфографии
Введите без ввода: завершить программу
Несколько слов + enter: отображать предложения по написанию
Введите без ввода: завершить программу
строка без пробелов + enter: отображать сегментированное слово текст
Введите без ввода: завершить программу
Проекты демонстрации, демокомплекс и сегментация, которые могут быть созданы с помощью бесплатного кода Visual Studio, который работает в Windows, MacOS и Linux.
//create object
int initialCapacity = 82765 ;
int maxEditDistanceDictionary = 2 ; //maximum edit distance per dictionary precalculation
var symSpell = new SymSpell ( initialCapacity , maxEditDistanceDictionary ) ;
//load dictionary
string baseDirectory = AppDomain . CurrentDomain . BaseDirectory ;
string dictionaryPath = baseDirectory + " ../../../../SymSpell/frequency_dictionary_en_82_765.txt " ;
int termIndex = 0 ; //column of the term in the dictionary text file
int countIndex = 1 ; //column of the term frequency in the dictionary text file
if ( ! symSpell . LoadDictionary ( dictionaryPath , termIndex , countIndex ) )
{
Console . WriteLine ( " File not found! " ) ;
//press any key to exit program
Console . ReadKey ( ) ;
return ;
}
//lookup suggestions for single-word input strings
string inputTerm = " house " ;
int maxEditDistanceLookup = 1 ; //max edit distance per lookup (maxEditDistanceLookup<=maxEditDistanceDictionary)
var suggestionVerbosity = SymSpell . Verbosity . Closest ; //Top, Closest, All
var suggestions = symSpell . Lookup ( inputTerm , suggestionVerbosity , maxEditDistanceLookup ) ;
//display suggestions, edit distance and term frequency
foreach ( var suggestion in suggestions )
{
Console . WriteLine ( suggestion . term + " " + suggestion . distance . ToString ( ) + " " + suggestion . count . ToString ( " N0 " ) ) ;
}
//load bigram dictionary
string dictionaryPath = baseDirectory + " ../../../../SymSpell/frequency_bigramdictionary_en_243_342.txt " ;
int termIndex = 0 ; //column of the term in the dictionary text file
int countIndex = 2 ; //column of the term frequency in the dictionary text file
if ( ! symSpell . LoadBigramDictionary ( dictionaryPath , termIndex , countIndex ) )
{
Console . WriteLine ( " File not found! " ) ;
//press any key to exit program
Console . ReadKey ( ) ;
return ;
}
//lookup suggestions for multi-word input strings (supports compound splitting & merging)
inputTerm = " whereis th elove hehad dated forImuch of thepast who couqdn'tread in sixtgrade and ins pired him " ;
maxEditDistanceLookup = 2 ; //max edit distance per lookup (per single word, not per whole input string)
suggestions = symSpell . LookupCompound ( inputTerm , maxEditDistanceLookup ) ;
//display suggestions, edit distance and term frequency
foreach ( var suggestion in suggestions )
{
Console . WriteLine ( suggestion . term + " " + suggestion . distance . ToString ( ) + " " + suggestion . count . ToString ( " N0 " ) ) ;
}
//word segmentation and correction for multi-word input strings with/without spaces
inputTerm = " thequickbrownfoxjumpsoverthelazydog " ;
maxEditDistance = 0 ;
suggestion = symSpell . WordSegmentation ( input ) ;
//display term and edit distance
Console . WriteLine ( suggestion . correctedString + " " + suggestion . distanceSum . ToString ( " N0 " ) ) ;
//press any key to exit program
Console . ReadKey ( ) ; Sympell Targets .net Standard v2.0 и может использоваться в:
Проекты Sympell, Demo, Democompound и Benchmark могут быть созданы с помощью бесплатного кода Visual Studio, который работает в Windows, MacOS и Linux.
Качество словаря имеет первостепенное значение для качества коррекции. Для достижения этих двух источников данных были объединены с помощью пересечения: Google Books NGRAM Данные, которые предоставляют репрезентативные частоты слов (но содержит много записей с ошибками правописания) и Showl - Списки, ориентированные на проверку орфографии, которые обеспечивают подлинный английский словарь (но не содержали частоты слов. Требуется для ранжирования предложений в пределах того же расстояния редактирования).
Clatess_dictionary_en_82_765.txt был создан путем пересечения двух списков, упомянутых ниже. Обратно отфильтровывая только те слова, которые появляются в обоих списках, используются. Дополнительные фильтры были применены, и полученный список усекнул до ≈ 80 000 наиболее частых слов.
Вы можете построить свой собственный частотный словарь для своего языка или специализированного технического домена. Алгоритм коррекции орфографии Sympell поддерживает языки с нелатиновыми персонажами, например, кирилли, китайский или грузинский.
Symspell включает в себя английский частотный словарь
Здесь расположены словари для китайского, английского, французского, немецкого, иврита, итальянского, русского и испанского:
Symspell.fretencydictionary
Частотные словаря во многих других языках можно найти здесь:
Репозиторий частот слов
Частотные словаря
Частотные словаря
C# (исходный исходный код)
https://github.com/wolfgarbe/symspell
.Net (пакет Nuget)
https://www.nuget.org/packages/symspell
Следующие сторонние порты или переопределения на другие языки программирования не были протестированы мне, будь то точный порт, без ошибок, предоставляют идентичные результаты или так же быстро, как исходный алгоритм.
Большинство портов Target Symspell версии 3.0 . Но версия 6.1. Обеспечивает гораздо более высокую скорость и снижение потребления памяти!
Webassembly
https://github.com/justinwilaby/spellchecker-wasm
Веб -API (Docker)
https://github.com/leonerath/symspellapi (версия 6.3)
C ++
https://github.com/athes21/symspellcpp (версия 6.5)
https://github.com/erhanbaris/symspellplusplus (версия 6.1)
Кристалл
https://github.com/chenkovsky/aha/blob/master/src/aha/sym_spell.cr
Идти
https://github.com/sajari/fuzzy
https://github.com/eskriett/spell
Хаскелл
https://github.com/cbeav/symspell
Ява
https://github.com/mightguy/customized-symspell (версия 6.6)
https://github.com/rxp90/jsymspell (версия 6.6)
https://github.com/lundez/javasymspell (версия 6.4)
https://github.com/rxp90/jsymspell
https://github.com/gpranav88/symspell
https://github.com/searchhub/predict
https://github.com/jpsingarayar/spellblaze
JavaScript
https://github.com/mathieuloutre/node-symspell (версия 6.6, нужен node.js)
https://github.com/itslenny/symspell.js
https://github.com/dongyuwei/symspell
https://github.com/icecreamyou/symspell
https://github.com/yomguithereal/mnemonist/blob/master/symspell.js
Джулия
https://github.com/arkoniak/symspell.jl
Котлин
https://github.com/wavesonics/symspellkt
Объектив-c
https://github.com/amitbhavsariphone/symspell (версия 6.3)
Питон
https://github.com/mammothb/symspellpy (версия 6.7)
https://github.com/viig99/symspellcpppy (версия 6.5)
https://github.com/zoho-labs/symspell (Python Bindings of Rust Version)
https://github.com/ne3x7/pysymspell/ (версия 6.1)
https://github.com/ayyuriss/symspell
https://github.com/ppgmg/github_public/blob/master/spell/symspell_python.py
https://github.com/rcourivaud/symspellcompound
https://github.com/esukhia/sympound-python
https://www.kaggle.com/yk1598/symspell-pell-corrector
Рубин
https://github.com/philt/symspell
Ржавчина
https://github.com/reneklacan/symspell (версия 6.6, компилируется для webassembly)
https://github.com/luketpeterson/fuzzy_rocks (постоянное хранилище данных, поддерживаемое Rocksdb)
Скала
https://github.com/semkath/symspell
Быстрый
https://github.com/gdetari/symspellswift
Контекстуальная многоязычная проверка орфографии для пользовательских запросов
Sanat Sharma, Josep Valls-Vargas, Tracy Holloway King, Francois Guerin, Chirag Arora (Adobe)
https://arxiv.org/abs/2305.01082
Контекст, чувствительная к проверке орфографии в реальном времени с адаптивностью языка
Прабхакар Гупта (Amazon)
https://arxiv.org/abs/1910.11242
Speakger: мета-дата, обогащенный речевым корпусом штата Германии и федеральных парламентов
Kai-Robin Lange и Carsten Jentsch
https://arxiv.org/pdf/2410.17886
Расширенная последовательность, тегивая словарь для грамматической коррекции ошибок
Стюарт Мешам, Кристофер Брайант, Марек Рей, Чжэн Юань
https://arxiv.org/abs/2302.05913
Германский парламентский корпус (Gerparcor)
Джузеппе Абрами, Мевлют Багси, Леон Хаммерла, Александр Мехлер
https://arxiv.org/abs/2204.10422
IOCR: Информированное распознавание оптического персонажа для выборов.
Кеннет У. Ойибо, Джин Д. Луи, Хуан Э. Гилберт
https://arxiv.org/abs/2208.00865
Проверка орфографии Amasigh с использованием алгоритма Damerau-levenshtein и N-грамма
Youness Chaabi, Fadoua Ataa Allah
https://www.sciencedirect.com/science/article/pii/s1319157821001828
Обследование коррекции запросов для поиска информации, ориентированной на тайский бизнес
Phongsathorn Kittiworapanya, Nuttapong Saelek, Anuruth Lertpiya, Tawunrat Chalothorn
https://ieeexplore.ieee.org/document/9376809
Sympell и LSTM на основе заклинателей для тамильца для тамильца
Сельвакумар Муругантамил Арасан Бактхаваламтамил Арасан Бактхаваламалайканнан Санкарасуббу
https://www.researchgate.net/publication/349924975_symspell_and_lstm_based_spell-_checkers_for_tamil
Symspell4burmese: Симметричный алгоритм коррекции орфографии для удаления (Sympell) для бирманской проверки орфографии
Ei phyu phyu mon; Ye kyaw thu; Чем Ю; Да, вай оо
https://ieeexplore.ieee.org/document/9678171
Проверка орфографии Индонезия Менггунакан Норвиг Дэн Симплль
Ясир Абдур Роман
https://medium.com/@yasirabd/spell-check-indonesia-menggunakan-norvig-dan-symspell-4fa583d62c24
Analisis perbandingan metode burkhard keller tree dan dan symspell dalam correction bahasa Индонезия
Мухаммед Хафиц Фердианси, я Кадек Дви Ньяна
https://ejournal.unesa.ac.id/index.php/jinacs/article/download/50989/41739
Улучшение поиска документов с коррекцией орфографии для слабых и сфабрикованных индонезийских хадисов
Мухаммед Заки Рамадханкемас М Лхаксанакомс М. Лхаксмана
https://www.researchgate.net/publication/342390145_improving_document_retrieval_with_spelling_correction_for_weak_and_fabricated_indonesian-translated_hadith
Sympell 을 한글 맞춤법 교정 김희규 김희규 김희규
https://heegyukim.medium.com/symspell%EC%9D%84-%EC%9D%B4%EC%9A%A9%ED%95%9C-%ED%95%9C%EA%B8%80- %EB%A7%9E%EC%B6%A4%EB%B2%95-%EA%B5%90%EC%A0%95-3DEF9CA00805
Черновые переломы текстов. Эвристическая процедура для исправления данных OCR
Jens Bjerring-Hansen, Ross Deans Kristensen-McLachla2, Philip Diderichsen и Dorte Haltrup Hansen
https://ceur-ws.org/vol-3232/paper14.pdf
На пути к обработке естественного языка в качестве коррекции орфографии для автономных рукописных систем распознавания текста
Артур Флор де Соуза Нето; Байрон Лейт Дантас Безерра; и Алехандро Эктор Тоселли
https://www.mdpi.com/2076-3417/10/21/7711
Когда использовать OCR после коррекции для распознавания именованной организации?
Вин-Нам Хуинх, Ахмед Хамди, Антуан Дусет
https://hal.science/hal-03034484v1/
Автоматическая коррекция ошибок: оценка производительности инструментов проверки орфографии
A. Tolegonova
https://journals.sdu.edu.kz/index.php/nts/article/view/690
Zhaw-Cai: ансамблевый метод для швейцарской немецкой речи в стандартном немецком тексту
Малгорзата Анна Уласик, Мануэла Хурлиманн, Богумила Дубель, Ив Кауфманн,
Сайлас Рудольф, Ян Дериу, Кацирна Млинчик, Ханс-Петер Хаттер и Марк Сиэлибак
https://ceur-ws.org/vol-2957/sg_paper3.pdf
Программа ошибок кириллического слова на основе машинного обучения
Battumur, K., Dulamragchaa, U., Enkhbat, S., Altanhuyag, L. & Tumurbaraatar, P.
https://mongoliajol.info/index.php/jimdt/article/view/2661
Быстрый приблизительный поиск строк для викификации
Шимон Олевникзак, Джулиан Шимански
https://www.iccs-meeting.org/archive/iccs2021/papers/127440334.pdf
Rumedspellchecker: исправление орфографических ошибок для естественного русского языка в электронных медицинских картах с использованием методов машинного обучения
Dmitrii Pogrebnoi, Anastasia funkner, Sergey Kovalchuk
https://link.springer.com/chapter/10.1007/978-3-031-36024-4_16
Расширенная последовательность, тегивая словарь для грамматической коррекции ошибок
Стюарт Мешам, Кристофер Брайант, Марек Рей, Чжэн Юань
https://aclanthology.org/2023.findings-ecl.119.pdf
Поиск сходства адаптивного иммунного иммунного иммунного иммунного рецептора с помощью симметричного поиска удаления
Touchchai Chotisorayuth, Andreas Tiffeau-Mayer
https://arxiv.org/html/2403.09010v1
Открытие замаскированной токсичности: новый предварительный модуль для улучшения модерации контента
Джонни Чан, Yuming Li
https://www.sciencedirect.com/science/article/pii/s2215016124001225
bycycle -> bicycle (вместо by cycle )inconvient -> inconvenient (вместо i convent )Symspell предоставляется SeekStorm - высокопроизводительный поиск в качестве API службы и поиска
