Кіріспе
Көптеген компьютерлік бағдарламалық қамтамасының әріптерді тексеру мүмкіндігі. Әріптерді ұсыну – бұл көптеген компьютерлік бағдарламалық қамтамасында қате жазылған болуы мүмкін сөздерге ұқсас нұсқаларды табу үшін қолданылатын мүмкіндік. Әріптерді ұсыну мүмкіндіктері көбінесе интернеттік ізденіс жүйелерінде, мәтін редакторында, әріптерді тексеру бағдарламаларында, медициналық транскрипцияда, автоматты сұранысты қайта жасау кезінде және жиілік тізімі статистикасын есептеуде қолданылады.
Spelling suggestion is a feature of many computer software applications used to suggest plausible replacements for words that are likely to have been misspelled. Spelling suggestion features are commonly included in Internet search engines, word processors, spell checkers, medical transcription, automatic query reformulation, and frequency log statistics reporting.
Алгоритмдер
Кез келген орфографиялық тексерушінің мақсатты тілдегі сөздер туралы жалпы немесе арнайы біліммен (мысалы, медициналық сөздік сияқты) деректері болуы керек. Бұл деректер мыналардан құралуы мүмкін: барлық белгілі сөздердің сөздігі; дұрыс жазылатын типтік мәтінді қамтитын мәтін корпусы; жиі қате жазылатын сөздердің тізімі, онда қателерді түзетулермен сәйкестендіріледі; адамдардың мәтін енгізу журналдары, мысалы, танымал іздеу жүйелерінен алынған мәліметтер. Бұл, әдетте, көпшілік ресурстарынан жиналған материал, бірақ онда орфографиялық қателер болуы мүмкін. Сондай-ақ, адамдар орфографиялық ұсынысты қашан таңдайтыны немесе одан да ұқсас сұранысты қайталап беретіні туралы мәліметтер де қамтылуы мүмкін. Бұл дұрыс емес жазылған сөздерді сенімді түзетулермен байланыстыратын көпшілік картасын құруға көмектеседі. Жиі қате жазылатын сөздердің тізіміне, мүмкін, бірнеше сөзден тұратын тіркестер де енгізілуі мүмкін, және енгізілген сөздердің немесе тіркестердің тізімде бар-жоғын тексеруге болады. Егер түзетулерге дейінгі қателерді түзетуге арналған алдын ала жасалған карта болмаса, сөздікті пайдаланудың әдеттегі тәсілі – енгізілген сөз бен сөздіктегі әрбір сөз арасындағы өңдеу қашықтығын есептеу болып табылады. Левенштейн арақашықтығы метрикасы бір әріпті енгізуді, жоюды немесе басқа әріппен алмастыруды «өңдеу» деп қарастырады. Ал Дамерау-Левенштейн арақашықтығына көрші әріптерді алмастыру (транспозиция) қосылады. Егер кіріс сөз сөздіктегі сөзден 1 өңдеу қашықтығында болса, онда ол түзету ретінде өте ықтимал деп есептеледі, 2 қашықтықтағы сөздер аз ықтимал, ал 3 қашықтықтағы сөздер кейде ұсыныстарға қосылады, кейде назарда ұсталмайды. Мәтін корпусын белгілі сөздердің сөздігі ретінде қарастыруға болады, онда әр сөздің пайда болу жиілігі көрсетіледі. Бұл мәліметтер жазу ұсыныстарын сұрыптау үшін пайдаланылуы мүмкін. Мысалы, егер 1 қашықтықта бірнеше түзету ұсынысы болса, корпуста жиі кездесетін сөздер қажетті түзетулер болуы мүмкін. Белгілі сөздердің сөздігі өте үлкен болғандықтан, кіріс сөз бен сөздіктегі әрбір сөз арасындағы өңдеу қашықтығын есептеу көп есептеу ресурстарын қажет етеді және салыстырмалы түрде баяу болады. Сақтау іздеулерін жылдамдату үшін BK ағаштары сияқты әртүрлі дерек құрылымдарын пайдалануға болады. Питер Норвиг ұсынған жылдам тәсіл кіріс сөзден барлық мүмкін өңдеулердің барлық пермутацияларын жасайды. Ұзындығы n сөз үшін және а әліпби өлшемі үшін, өңдеу қашықтығы 1 үшін ең көп дегенде n өшіру, n-1 транспозиция, a*n өзгеріс және a*(n+1) енгізу болады. Ағылшын алфавитіндегі 26 әріпті ғана пайдалансақ, бұл тек 54*n+25 сөздік іздеуін береді, кез келген қайталануды алып тастағанда (бұл сөздегі нақты әріптерге байланысты). Бұл жүздеген мың сөздікпен салыстырғанда салыстырмалы түрде аз. Дегенмен, 2 және одан үлкен арақашықтықты өңдеу үшін ондаған немесе жүздеген мың іздеулер қажет болуы мүмкін. Вольф Гарбтың тағы бір жаңалығы – SymSpell деп аталады. Басқалар үлкен көлемде деректерді және терең оқыту әдістерін (машиналық оқытудың бір түрі) қолдану арқылы нейрондық желілерді орфографиялық түзетуді орындауға үйрету үшін тәжірибе жүргізді.
A dictionary of all known words. A text corpus which includes typical text, known to be correctly spelled. A list of frequently misspelled words, mapping errors to corrections. Logs of human text input, such as from a popular search engine. This is essentially a crowdsourced corpus, but it is assumed there will be some spelling mistakes. Data might be included about when people click on a spelling suggestion or make a second, very similar query; this creates a crowdsourced mapping of misspelled words to reliable corrections. A list of frequently misspelled words, possibly including multi word phrases, can simply be consulted to see if any of the input words or phrases are listed. To make use of a dictionary without a pre existing mapping from misspellings to corrections, the typical technique is to calculate the edit distance between an input word and any given word in the dictionary. The Levenshtein distance metric considers an "edit" to be the insertion, deletion, or substitution (with another letter) of one letter. The Damerau–Levenshtein distance adds transpositions (the swapping of neighboring letters). Dictionary words that are an edit distance of 1 away from the input word are considered highly likely as corrections, edit distance 2 less likely, and edit distance 3 sometimes included in suggestions and sometimes ignored. A text corpus can be summed up as a dictionary of known words, with a frequency of appearance for each word. This can be used to sort the spelling suggestions. For example, if there are multiple suggestions of edit distance 1, the words that appear most frequently in the corpus are most likely to be the desired correction. Because a dictionary of known words is very large, calculating the edit distance between an input word and every word in the dictionary is computationally intensive and thus relatively slow. Various data structures can be utilized to speed up storage lookups, such as BK trees. A faster approach adopted by Peter Norvig generates all the permutations from an input word of all possible edits. For a word of length n and an alphabet of size a, for edit distance 1 there are at most n deletions, n 1 transpositions, a*n alterations, and a*(n+1) insertions. Using only the 26 letters in the English alphabet, this would produce only 54*n+25 dictionary lookups, minus any duplicates (which depends on the specific letters in the word). This is relatively small when compared to a dictionary of hundreds of thousands of words. However, tens or hundreds of thousands of lookups might be required for edit distance 2 and greater. A further innovation adopted by Wolf Garbe, known as SymSpell
Others have experimented with using large amounts of data and deep learning techniques (a form of machine learning) to train neural networks to perform spelling correction.