Orfoqrafiya Təklifi#3100
Orfoqrafik təklif proqramının bir hissəsi, səhv yazılmış sözlər üçün mümkün əvəzetmələr yaradır. Bu əvəzetmələrin uyğunluğunu ölçmək üçün onların səhv yazılmış sözlə olan redaktə məsafəsi hesablanır. İki söz arasındakı redaktə məsafəsi, bir sözü digərinə çevirmək üçün lazım olan əməliyyatların ümumi sayıdır. Bu əməliyyatlar — bir simvolun əlavə olunması, silinməsi, əvəzlənməsi və ardıcıl 2 simvolun yer dəyişdirilməsindən ibarətdir (transpozisiya).
Məsələn, "wonder" sözündə 'o' simvolu silinərsə, söz "wnder" olar. 'o' simvolu 'a' ilə əvəzlənərsə, söz "wander" olar. "er" simvollarında transpozisiya tətbiq edilərsə, söz "wondre" olar.
Bu redaktə məsafəsi strategiyasında, iki söz arasındakı oxşarlıq onların minimal redaktə məsafəsindən asılıdır. Əgər word_1 və word_2 arasındakı minimal redaktə məsafəsi word_1 və word_3 arasındakından azdırsa, onda word_1 word_2-yə word_3-dən daha çox bənzəyir. Beləliklə, word_2 word_1 üçün word_3-ə nisbətən daha yaxşı yazım təklifidir.
Tutaq ki, siz proqram təminatı şirkətində işləyirsiniz və orfoqrafik təklif proqramının prototipini hazırlamalısınız. Bu prototip söz emalı proqramının bir hissəsi olacaq. Tələblərə görə, təkliflər üçün redaktə məsafəsi strategiyasından istifadə edilməlidir. Lakin əvəzləmə əməliyyatı ən çox rast gəlinən yazı səhvlərinə uyğunlaşdırılmalıdır. Bir simvolun başqa bir simvolla əvəz olunmasının dəyəri klaviatura əyarındakı yerlərindən asılıdır. Əgər simvollar bir-birinə yaxın yerləşirsə, dəyəri standart əvəzləmədən yarım qat azdır. Bu məqsədlə, əvəzləmələr yaxın əvəzləmə (near-substitution) və uzaq əvəzləmə (far-substitution) kimi təsnif edilir. Onların dəyərləri müvafiq olaraq 1 və 2 olaraq təyin edilir. Daxiletmə, silmə və transpozisiya əməliyyatlarının hər biri üçün dəyər isə 2-dir. Bundan əlavə, proqram menecerinizin qəbul etdiyi vaxt limitinə uyğun olmalıdır. Bu prototip üçün İngilis QWERTY klaviatura düzülüşü seçilmişdir.
Məqsəd
Hər bir daxil edilən söz üçün optimal orfoqrafik təklifləri yaradın; burada hər bir optimal təklif lüğətdə ən kiçik redaktə məsafəsinə malik sözdür. 5,000 səhv yazılmış söz üçün ayrılmış zaman limiti ən çoxu 5 dəqiqədir.
Giriş standart girişdən ibarətdir və 3 hissədən ibarətdir. Hər üç hissə boş sətr ilə bitir.
Birinci hissə yaxın əvəzləmə qaydalarıdır, burada hər qayda bir sətrdədir. Hər sətr iki sahədən ibarətdir, aralarındakı boşluqla ayrılır. Qaydaların ümumi sayı ən çoxu 150-dir.
Birinci sahə başqa simvollarla yaxın əvəz olunabilən simvoldur.
İkinci sahə həmin simvol üçün yaxın əvəzləməyə icazə verilən simvollar ardıcıllığıdır. Bu sahədə boşluq yoxdur.
Bu hissədə istifadə edilə bilən simvollar — əlifba, rəqəmlər və müəyyən durğu işarələri daxil olmaqla, ingilis klaviaturasına uyğundur (boşluq və tab istisna olmaqla). Siyahı aşağıdakıdır:
abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789' !@#$%^6*()-_=+|[{]};:'”,003c.003e/?
İkinci hissə lüğətdəki sözlərin siyahısıdır, hər biri bir sətrdədir. Lüğətdəki sözlərin sayı 150,000-dən çox olmur.
Lüğət sözlərində istifadə olunan simvollar: əlifba simvolları və apostrof (’).
abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ’
Üçüncü hissə — hər biri ayrıca sətrdə olan, təklif alınacaq sözlərin siyahısıdır. Sözlərin sayı 5,000-dən çox olmur.
Bu hissəyə daxil ola bilən simvollar birinci hissədəki simvollarla eynidir: əlifba, rəqəmlər və bəzi durğu işarələri. (Birinci hissəyə baxın.)
Hər üç hissə boş sətr ilə bitdiyindən, üçüncü boş sətr girişin bitdiyini göstərir.
Üçüncü hissədəki hər söz üçün aşağıdakı 3 informasiyanı iki nöqtə ilə ayrılmış bir sətrə yazın:
Birinci hissə — daxil edilən söz.
İkinci hissə — daxil edilən və təklif olunan söz(lər) arasındakı minimal redaktə məsafəsi.
Üçüncü hissə — təklif olunan söz(lər) siyahısı, artan sıra ilə boşluqla ayrılmış; son sözdən sonra artıq boşluq olmadan.
Əlavə İzah
Nümunə girişində 5 yaxın əvəzləmə qaydası (sətr 1-5), 10 lüğət sözü (sətr 7-16) və 12 təklif alınan söz (sətr 18-29) var.
Nümunə çıxışında, müvafiq 12 söz üçün 12 sətr var.
1-ci söz üçün x və onun təklifləri (A B Z a b) arasındakı minimal redaktə məsafəsi 2-dir. Bunların hamısı uzaq əvəzləmə xərcləridir.
2-ci söz üçün s və təklifi (a) arasındakı minimal məsafə 1-dir — birinci əvəzləmə qaydasına əsasən yaxın əvəzləmə xərci.
3-cü söz üçün z və təklifləri (A Z a) arasında minimal məsafə 1-dir, birinci və ya beşinci əvəzləmə qaydasına əsasən yaxın əvəzləmə xərci.
4-cü söz üçün minimal redaktə məsafəsi 4-dür, bir uzaq əvəzləmə və bir silmə xərci.
5-ci söz üçün minimal məsafə 6-dır: xxx və (A B Z a b) üçün iki silmə və bir uzaq əvəzləmə xərci; xxx və ABC üçün isə üç uzaq əvəzləmə xərci.
6-cı söz üçün angre və anger arasında bir transpozisiya xərci; angre və (angle angry) arasında isə bir uzaq əvəzləmə xərci var.
7-ci və 8-ci sözlər oxşardır. 7-ci üçün məsafə bir uzaq əvəzləmədir. angrt və anger üçün isə iki yaxın əvəzləmə tətbiq olunur (r e və t r), dördüncü yaxın əvəzləmə qaydasına əsasən.
9-cu söz tam şəkildə lüğətdə var, məsafə 0-dır.
10 və 11-ci söz üçün minimal məsafə hər biri üçün bir transpozisiyadır.
12-ci söz üçün CAB və (A B) arasında iki silmə xərci; CAB və (ABC) arasında isə bir silmə və bir əlavə xərci var. Qeyd edək ki, bu, CAB-dan ACB-yə və sonra ACB-dən ABC-yə iki transpozisiya kimi qiymətləndirilmir.
Nümunə 1