Spelling: matnlarni orfografik tekshirish

Hozirgi kunda matnlarga ishlov berish dasturlashning asosiy masalalaridan biri hisoblanadi. Eng ommabop va foydali vazifalardan biri bu — matnlarni orfografik hatoliklarga tekshirish. Ushbu maqolada matnlarni orfografik hatoliklarga tekshirishda qo'llaniladigan algoritmlardan biri haqida to'xtalib o'tmoqchiman.
Bu masalada bizga juda ko'plab algoritmlar va ma'lumotlar tuzilmasi yordam beradi: Levenshteyn masofasi, hesh jadvallar, BK-tree, Bloom filter kabilar umumiy algoritm qurishda ko'p ishlatiladi. Eng mashxurlaridan biri Levenshtein distance (Levenshteyn masofasi) algoritmi ham keng qo'llaniladi. PHPda bir funksiya bor:

int levenshtein(string $str1, string $str2)

bu funksiya $str1 so'zni $str2 dan qanchalik uzqoliligini aniqlaydi. Juda foydali funksiya, bu Levenshtein distance algoritmi asosida ishlaydi. Bu funksiya juda ko'p parserlarda menga yordami tekkan. Masalan:

protected function getSimilarWordByLevenshtein($array, $word, $depth = NULL)
{
        $shortest = -1;
        $closest  = FALSE;
        if ($depth === NULL) {
                $depth = strlen($word) / 1.3;
        }

        foreach ($array as $index => $value) {
                $lev = levenshtein($word, $value);
                if ($lev == 0) {
                        $closest  = $value;
                        $shortest = $lev;
                        break;
                }

                if (($lev <= $shortest || $shortest < 0) && ($lev < strlen($value) / $depth)) {
                        $closest  = $value;
                        $shortest = $lev;
                }
        }
        if ($shortest < $depth) return $closest;
        return FALSE;
}

Bu logikani $array massivida berilgan so'zlar (csv ustunlari, yoki product attribut qiymatlari) ichidan $word so'ziga eng o'xshaganini topishda ishlatib ko'rsak bo'ladi. Va hokazo.

Google spelling

Ayni damda to'xtalib o'tmoqchi bo'lganim berilgan so'zga shakl jihatdan eng o'xshash so'zlarni qidirishda qo'llaniladigan ulumlashtirilgan algoritm haqida to'xtalmoqchiman. Buni ko'pchilik Google ishlatadigan texnologiya deb ham atashadi. Masalan Google qidiruviga imloviy hato so'z kiritsak, did you mean ...? ko'rinishida to'gri variantlarini taqdim etadi. Bu imkoniyat hozirda deyarli barcha ilg'or dasturlarda ishlatimoqda: qidiruv tizimlari, office paketlari, brauzerlar, dasturlash IDE lari, mobil telefonlarda ham hatto. Bu haqda Peter Norveg o'zining ushbu ishida batafsil to'xtalib o'tgan.
Algoritm juda ham sodda, sinchiklab o'rgansangiz ixtiyoriy tilda implementatsiya qila olasiz.

Asosiy bosqichlar

I. Bizda imloviy to'g'ri so'zlar bazasi (B) mavjud. So'zlar soni qancha ko'p bo'lsa berilgan hato so'zga taqdim etiladigan to'gri alternativalarini topish extimoli shuncha yuqori.

II. Berilgan hato so'z (W)ning eng yaqin (masofasi 1 ga teng bo'lgan) shakillari (A)ni hosil qilamiz. Bunda masofa 1 ga teng degani shu so'z bilan shaklan bitta belgiga farq qiladigan so'zlarni ya'ni alternativalarini generatsiya qilamiz. Generatsiya qilishda asosan 4 turdagi shakl o'zgarishini ishlatamiz: («masina» hato so'zi uchun misollarni keltrib o'taman)

1. Deletion — so'zdagi har bir harfni o'chirib chiqish:
   asina, msina, maina, masia, masin
2. Transposition — ikki yonma yon harfning o'rnini almashtirish:
   amsina, msaina, maisna, masnia, masian
3. Replacement — so'zdagi har bir harf o'rniga alfavitdagi harflarni qo'yib chiqish:
   aasina, basina, casina, ..., mabina, macina, madina, ..., malina,..., masinx (va hokazo, bu usulda hosil qilingan so'zlar soni juda ham ko'p, taxminan 6*26 ta, 6 — «masina» so'zi uzunligi, 26 — lotin alfavitidagi belgilar soni.)
4. Insertion — so'zga alfavitdagi belgilarni qo'shib chiqish:
   amasina, bmasina, ..., zmasina, ..., masgina, mashina, ..., maszina, ..., masinaa, ..., masinaz (va hokazo, bu usulda hosil qilingan so'zlar soni juda ham ko'p, taxminan 7*26 ta, ularni qisqartirdik).

Hozircha shu 4 usul yordamida generatsiya qilingan so'zlar yetarli, taxminan ularning umumiy soni 2*L*N, bu yerda L — kiritilgan so'z uzunligi, N — alfavitdagi belgilar soni. Ushbu hosil qilingan so'zlar berilgan so'zdan uzoqligi 1 ga teng bo'lgan so'zlar guruhi hisoblanadi. Chunki ularni hosil qilishda faqat bitta tahrirlash yetarli, ya'ni yoki o'chiramiz, yoki o'rnini almashtiramiz, yoki belgini almashtiramiz, yoki bitta belgi qo'shamiz.

III. Endi hosil bo'lgan alternativa (A)lar ichidan to'g'ri so'zlar bazasi (B)da mavjud bo'lgan so'zlarni ajratib olamiz. Bunda bizga juda ko'p sonli to'gri so'zlar orasidan hosil qilingan alternativa mavjudligini tekshirish kifoya. Tasavvur qiling, to'g'ri so'zlar bazasi (B)da M ta so'z mavjud, 1-uzoqlikdagi so'zlar soni esa 2*L*N ta, har bir alternativani M ta so'z ichidan qidirib chiqish, umumiy solishtirishlar soni o'rtacha L*N*M tani tashkil etadi. Bu anchagina hisoblash amallari degani. Bu yerda bizga har doimgidek ma'lumotlar tuzilmasi (Data Structure) yordamga keladi. Topingchi aynan qaysi tuzilma biz uchun eng tezkor hisoblanadi? Binar daraxtmi (Binar Tree), bog'langan ro'yhatlarmi (Linked List) yoki hesh jadvallarmi (Hash Maps)? Ushbu sahifada Java dasturlash tilida ishlatishimiz mumkin bo'lgan ma'lumotlar tuzilmasi xarakteristikalari berilgan. Tezkorligi bo'yicha albatta HeshMap ayni ushbu masalamizga to'liq javob beradi. Men LinkedList ni ham sinab ko'rdim, agar uzoqligi 1 ga teng bo'lgan alternativalar ichida to'g'ri so'zlar bo'lmasa, 2-uzoqlikdagi so'zlarni qidirishda LinkedList vaqtdan ancha yutqazdi. Buni siz ham sinab ko'rishingiz mumkin. Demak, to'g'ri so'zlar bazasi (B)ni HashMap ga joylaymiz, undan A so'zni qidirish murakkabligi O(1) ga teng, ya'ni bitta qadam bilan to'g'ri so'zlar bazasida A so'z mavjud yoki yo'qligini aniqlash mumkin. Demak, HashMap ni qo'llasak kiritilgan hato so'zni to'gri alternativalarini topish murakkabligi o'rtacha 2*L*N ga teng bo'lar ekan.

IV. Agar (III) qadamda biror bir natija topilmasa, yani uzoqligi 1 ga teng bo'lgan so'zlar ichidan to'gri so'z topilmasa uzoqligi 2 ga teng bo'lgan so'zlarni generatsiya qilamiz, bunda albatta natija chiqishi aniq. Demak (II) qadamda hosil qilingan har bir so'z uchun yana (II) qadam yordamida uni o'zgartirib chiqamiz. Bunda jami hosil bo'lgan alternativalar soni o'rtacha 4*L²*N² tani tashkil etadi. Endi uzoqligi 3 ga teng bo'lgan (ya'ni tahrirlash 3 marta amalga oshirilgan) so'zlar sonini tasavvur qilavering qanchalik ko'p bo'lishini. Umuman olganda real hayotda maksimum uzoqligi 2 ga teng bo'lgan so'zlar qidiriladi. Ya'ni bir so'zni yozar ekansiz, unda hato qilish darajasi juda kam, ya'ni, bitta so'zda maksimum 2 ta bo'lishi mumkin. Masalan, siz algoritm deb yozmoqchisiz, hato qilsangiz: algorimt, algoitm, kabi hato qilasiz, bundan daxshatli bo'lishi kamdan kam. Yoki bitta xarf tushib qoladi, yoki 2 ta qo'shni harf o'rni almashib qoladi, yoki bitta harf qo'shilib qoladi. Demak, kelishib oldik, bizga uzog'i bilan 2 ta tahrirlash yetarli.

Endi ushbu qoidalarni dasturlash yordamida yozib chiqaylik, men bunda Java (7-versiyasi)dan foydalandim. Imloviy behato so'zlar bazasi sifatida o'zbek lotin alfavitidagi soni 11000 tacha bo'lgan so'zlar bazasini ishlatdim. Yoqoridagi qadamlarni qisqacha kommentariyada keltirib o'tdim.

Dastur kodi

import java.io.*;
import java.nio.charset.StandardCharsets;
import java.nio.file.Files;
import java.nio.file.Paths;
import java.util.*;
/**
 * Java SE 7
 * Created with IntelliJ IDEA.
 * User: Shavkat
 * Date: 12/2/13
 * Time: 8:26 PM
 */
public class Spell {
    //lexiconWordListBase - o'zbek tilidagi so'zlar ro'yhati, uni fayldan yuklab olamiz
    protected static HashMap<String, String> lexiconWordListBase;
    protected String fileName = "words.txt";

    //o'zbek lotin alfavitidagi belgilar ro'yhati
    protected String alphabet = "abcdefghijklmnopqrstuvxyz'";

    //dastruning boshlanish qismi
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String someWord = in.nextLine();
        Spell processor = new Spell();

        //o'xshash so'zlarni qidiramiz
        List<String> similarWords = processor.getSimilarWords(someWord);
        System.out.println(similarWords);
    }

    /**
     * Asosiy qism. Bu yerda berilgan so'zga o'xshash so'zlar qidiriladi.
     *
     * @param word
     * @return
     */
    protected List getSimilarWords(String word) {
        ArrayList<String> result = new ArrayList<String>();
        //1-tahrirlash
        if (lexiconWordListBase.containsKey(word)) {
            result.add(word);
        } else {
            List<String> alternatives = this.getAlternatives(word);
            //System.out.println(alternatives.toString());
            for (String similarWord : alternatives) {
                if (lexiconWordListBase.containsKey(similarWord) 
                    && !result.contains(similarWord)&& similarWord.length() > 1)
                    result.add(similarWord);
            }

            //2-tahrirlash, agar birinchi qidiruvda ham alternativ so'zlar ro'yhati bo'sh bo'lsa
            if (result.size() == 0) {
                List<String> subAlternatives;
                //1-tahrirlashda olingan har bir alternativ so'z uchun uning 
                //o'xshash alternativalarini ko'rib chiqamiz
                for (String alternativeWord : alternatives) {
                    subAlternatives = this.getAlternatives(alternativeWord);
                    //System.out.println(subAlternatives);
                    for (String similarWord : subAlternatives) {
                        if (lexiconWordListBase.containsKey(similarWord)  
                            &&!result.contains(similarWord) && similarWord.length() > 1)
                            result.add(similarWord);
                    }
                }
            }
        }
        return result;
    }

    /**
     * Berilgan word so'zga alternativ so'zlarni hosil qilish
     *
     * @param word
     * @return ArrayList
     */
    protected ArrayList getAlternatives(String word) {
        ArrayList<String> alternatives = new ArrayList<String>();
        int length = word.length();

        //Deletion - So'zdagi harflarni o'chirilgan kombinatsiyasi
        for (int i = 0; i < length; i++) {
            alternatives.add(word.substring(0, i) + word.substring(i + 1));
        }
        //Transposition - So'zdagi ikki qo'shni harfni o'rnini almashtirish
        for (int i = 0; i < length - 1; i++) {
            alternatives.add(word.substring(0, i) + word.charAt(i + 1) + word.charAt(i) + word.substring(i + 2));
        }
        //Replacement - So'zdagi har bir harf o'rniga alfavitdagi harflarni qo'yib chiqish
        for (int i = 0; i < length - 1; i++) {
            for (char character : alphabet.toCharArray()) {
                if (character != word.charAt(i))
                    alternatives.add(word.substring(0, i) + character + word.substring(i + 1));
            }
        }
        //Insertion - So'zga alfavitdagi belgilarni qo'shib chiqilgan kombinatsiyasi
        for (int i = 0; i < length - 1; i++) {
            for (char character : alphabet.toCharArray()) {
                alternatives.add(word.substring(0, i) + character + word.substring(i));
            }
        }
        return alternatives;
    }


    public Spell() {
        if (lexiconWordListBase == null) {
            try {
                //Agar siz Java SE 6 versiysini ishlatayotgan bo'lsangiz:
                //this.loadDataInJava6();
                //Agar siz Java SE 7 versiysini ishlatayotgan bo'lsangiz:
                this.loadDataInJava7();
            } catch (IOException e) {
                System.out.println(e.getMessage());
            }
        }
    }

    /**
     * Bu metod loadDataInJava6 da keltirilgan standart BufferedReader ga nisbatan tezroq ishlaydi,
     * agar sizda Java SE 7 versiyasi bo'lsa
     *
     * @throws IOException
     */
    protected void loadDataInJava7() throws IOException {
        List<String> lines = Files.readAllLines(Paths.get(this.fileName), StandardCharsets.UTF_8);
        lexiconWordListBase = new HashMap<String, String>();
        for (String word : lines) {
            lexiconWordListBase.put(word, word);
        }
    }

    protected void loadDataInJava6() throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new FileReader(this.fileName));
        lexiconWordListBase = new HashMap<String, String>();
        String word;
        while ((word = bufferedReader.readLine()) != null) {
            lexiconWordListBase.put(word, word);
        }
        bufferedReader.close();
    }
}

Natijalar

masina[madina, malina, mashina]

begubor[beg'ubor]

guzal[zal, azal, gal, gul, yuza, afzal, tugal, g'azal, go'zal]

loyha[loyqa, loyiha]

P.S. Bu usul ingliz tili uchun juda ham qulay, chunki ingliz tilida qo'shimchalar ham alohida so'z sifatida ifodalanadi. O'zbek va rus tillarida esa unday emas, yangi bir qo'shimcha qo'shish orqali so'z formasi o'zgaradi. Aytmoqchi bo'lganim o'zbek tilida to'g'ri so'zlar bazasini qurib chiqish juda ham murakkab jarayon, agar qo'shimchasiz so'zlarning o'zini o'rtacha 100000 ta atrofi hisoblasak, bitta so'zga 10 dan ortiq qo'shimcha qo'shish orqali uning kamida 15 ta shaklini yasash mumkin. Natijada to'g'ri so'zlar bazasida o'zbek tili uchun 1.5-2 million atrofida so'z yig'ish kerak bo'ladi. Keyingi maqolalarda bloggerlarimiz matn tahrirlash, orfografika, tarjima, lug'at kabi masalalarni hal qilishda aynan ona tilimizni qo'llab quvvatlash nuqtai nazaridan yondoshib maqolalar keltirib o'tsa juda ham yaxshi ish bo'lar edi.