Prolog

Selamat siang, para pembaca yang budiman. Pada artikel ini saya akan berbicara tentang bagaimana mengurai angka yang ditulis dalam kata-kata dalam bahasa Rusia.

Smart parser ini memungkinkan untuk mengekstraksi angka dari teks dengan kesalahan yang dibuat sebagai akibat dari input yang salah atau sebagai hasil dari pengenalan optik teks dari suatu gambar (OCR).

Untuk yang malas:
Tautan ke proyek github: tautan .

Dari algoritma ke hasil

Bagian ini akan menjelaskan algoritma yang digunakan. Perhatian, banyak surat!

Pernyataan masalah

Di tempat kerja, saya perlu mengenali teks dari dokumen cetak yang difoto dengan kamera smartphone / tablet. Karena perjanjian non-pengungkapan, saya tidak bisa memberikan contoh foto, tetapi intinya adalah dokumen memiliki tabel di mana indikator tertentu ditulis dalam angka dan kata-kata, dan data ini harus dibaca. Parsing teks dalam kata-kata diperlukan sebagai alat validasi tambahan untuk memastikan bahwa nomor tersebut dikenali dengan benar. Tapi, seperti yang Anda tahu, OCR tidak menjamin pengenalan teks yang akurat. Misalnya, angka dua puluh, yang ditulis dengan kata-kata, dapat dikenali sebagai "dvupat" atau bahkan sebagai "dvupat". Hal ini diperlukan untuk memperhitungkan hal ini dan mengekstraksi jumlah informasi maksimum, mengevaluasi besarnya kesalahan yang mungkin terjadi.

Catatan Untuk pengenalan teks, saya menggunakan tesseract 4. Untuk .NET, tidak ada paket NuGet siap pakai dari versi keempat, jadi saya membuat satu dari cabang proyek utama, yang dapat berguna: Genesis.Tesseract4 .

Algoritma parsing angka dasar

Mari kita mulai dengan yang sederhana, yaitu dengan algoritma pengenalan teks yang ditulis dalam kata-kata, sejauh ini tanpa kesalahan. Jika Anda tertarik untuk parsing pintar, lewati bagian ini.

Saya tidak terlalu bagus dalam googling, jadi saya tidak segera menemukan algoritma yang sudah jadi untuk menyelesaikan masalah ini. Namun, ini bahkan menjadi lebih baik, karena sebuah algoritma yang ditemukan oleh kami sendiri memberi lebih banyak ruang untuk pengkodean. Dan tugas itu sendiri ternyata menarik.

Jadi, mari kita ambil sejumlah kecil, misalnya, “seratus dua puluh tiga”. Ini terdiri dari tiga kata ( token ), yang masing-masing sesuai dengan angka, semua angka ini diringkas:

Sejauh ini, semuanya sederhana, tetapi kami menggali lebih dalam, misalnya, pertimbangkan angka "dua ratus dua belas ribu seratus lima."

Seperti yang dapat Anda lihat, ketika ada ribuan jumlahnya (serta jutaan dan derajat ribuan lainnya), jumlahnya dibagi menjadi beberapa bagian yang terdiri dari sejumlah kecil lokal, dalam contoh di atas - 212, dan sebuah faktor (1000). Mungkin ada beberapa fragmen seperti itu, tetapi mereka semua pergi dalam urutan pengganda, misalnya, seribu atau seribu tidak dapat mengikuti seribu. Ini juga berlaku untuk bagian-bagian dalam jumlah kecil, karena ratusan tidak dapat mengikuti ratusan dan puluhan, sehingga entri "seratus lima ratus" tidak benar. Kami akan menyebut karakteristik yang menghubungkan dua token dari jenis yang sama level , misalnya, token "seratus" dan "tiga ratus" memiliki satu level, dan itu lebih besar daripada token "fifty".

Dari pertimbangan ini, lahirlah gagasan tentang algoritma. Mari kita tuliskan semua token yang mungkin ( sampel ), yang masing-masingnya akan kita tentukan angka, serta dua parameter - level dan tanda pengali.

Bahkan, Anda dapat menambahkan token lain ke tabel ini, termasuk untuk bahasa asing, tapi jangan lupa bahwa di beberapa negara digunakan sistem penamaan yang panjang, bukan pendek.

Sekarang mari kita beralih ke parsing. Kami akan mendapatkan empat jumlah:

1. Tingkat global (globalLevel). Mengindikasikan level pengganda terakhir. Awalnya tidak terdefinisi dan perlu untuk kontrol. Jika kita menemukan token pengali yang levelnya lebih besar atau sama dengan global, maka ini adalah kesalahan.
2. Nilai global (globalValue). Total adder, di mana hasilnya adalah hasil dari mengalikan jumlah dan faktor lokal.
3. Tingkat lokal ( tingkat lokal ). Menunjukkan level apa yang dimiliki token terakhir. Awalnya tidak terdefinisi, bekerja serupa dengan level global, tetapi direset setelah ditemukannya pengali.
4. Nilai lokal ( Nilai lokal ) Penambah token yang tidak multiplier, yaitu nomor hingga 999.

Algoritma adalah sebagai berikut:

1. Pisahkan string menjadi token menggunakan "\ s +" biasa.
2. Kami mengambil token berikutnya, kami mendapatkan informasi tentang hal itu dari sampel.
3. Jika ini adalah pengganda:
   
   • Jika level global diatur, maka kami memastikan bahwa levelnya lebih besar atau sama dengan level token. Jika tidak, ini adalah kesalahan, angkanya salah.
   • Setel level global ke level token saat ini.
   • Lipat gandakan nilai token dengan nilai lokal dan tambahkan hasilnya ke nilai global.
   • Kami menghapus nilai dan level lokal.
4. Jika ini bukan pengganda:
   
   • Jika level lokal diatur, maka kami memastikan bahwa levelnya lebih besar atau sama dengan level token. Jika tidak, ini adalah kesalahan, angkanya salah.
   • Setel level lokal ke level token saat ini.
   • Tambahkan nilai token ke nilai lokal.
5. Kami mengembalikan hasilnya sebagai jumlah nilai global dan lokal.

Contoh pekerjaan untuk angka "dua juta dua ratus dua belas ribu seratus delapan puluh lima."

Hasilnya akan menjadi 2.212.185.

Penguraian pintar

Algoritma ini dapat digunakan untuk mengimplementasikan perbandingan lain, dan tidak hanya untuk parsing angka, untuk alasan ini saya akan mencoba menggambarkannya lebih terinci.

Dengan parsing nomor yang ditulis dengan benar tahu. Sekarang mari kita berpikir tentang kesalahan apa yang bisa terjadi jika angka yang diperoleh sebagai akibat dari OCR tidak ditulis dengan benar. Saya tidak mempertimbangkan opsi lain, tetapi Anda dapat memodifikasi algoritme untuk tugas tertentu.

Saya telah mengidentifikasi tiga jenis kesalahan yang saya temui dalam proses kerja:

1. Ganti karakter dengan orang lain dengan gaya yang mirip. Misalnya, huruf "c" untuk beberapa alasan diganti dengan "p", dan "n" oleh "dan" dan sebaliknya. Saat menggunakan tesseract versi ketiga, dimungkinkan untuk mengganti huruf "o" dengan nol. Kesalahan ini, begitu saja, adalah yang paling umum, dan memerlukan penyetelan untuk pustaka pengenalan tertentu. Jadi, prinsip kerja tesseract versi 3 dan 4 memiliki perbedaan utama, oleh karena itu kesalahan akan berbeda.
   
2. Token bergabung. Kata-kata dapat bergabung bersama (belum bertemu sebaliknya). Dalam kombinasi dengan kesalahan pertama, itu menghasilkan frase iblis seperti "ganda." Mari kita coba menjelekkan monster seperti itu juga.
   
3. Noise - karakter dan frasa kiri dalam teks. Sayangnya, ada sedikit yang bisa dilakukan saat ini, tetapi ada prospek ketika mengumpulkan statistik yang cukup signifikan.
   

Pada saat yang sama, algoritma parsing yang dijelaskan di atas hampir tidak berubah, perbedaan utamanya adalah memecah string menjadi token.

Tapi mari kita mulai dengan mengumpulkan beberapa statistik tentang penggunaan huruf dalam token. Dari 33 huruf bahasa Rusia, hanya 20 yang digunakan saat menulis bilangan bulat non-negatif, sebut saja mereka huruf baik :

13 sisanya, masing-masing, akan disebut huruf buruk . Ukuran maksimum token adalah 12 karakter (13 saat menghitung hingga kuadriliun). Substring yang lebih panjang dari nilai ini harus dibagi.

Untuk membandingkan string dan token, saya memutuskan untuk menggunakan algoritma Wagner-Fisher , meskipun saya menyebutnya nama Levenshtein dalam kode. Saya tidak memerlukan instruksi editorial, jadi saya menerapkan versi algoritma yang ramah memori. Saya harus mengakui bahwa implementasi algoritma ini ternyata menjadi tugas yang lebih sulit daripada parser itu sendiri.

Program pendidikan kecil: jarak Levenshtein adalah kasus khusus dari algoritma Wagner-Fisher, ketika biaya memasukkan, menghapus, dan mengganti karakter bersifat statis. Ini tidak begitu dalam tugas kita. Jelas, jika kita menemukan huruf yang buruk dalam substring, maka perlu diganti dengan huruf yang baik, tetapi mengganti yang baik dengan yang buruk sangat tidak diinginkan. Secara umum, itu tidak mungkin, tetapi situasinya tergantung pada tugas tertentu.

Untuk menjelaskan biaya memasukkan, menghapus, dan mengganti karakter, saya membuat tabel seperti ini: tautan ke tabel dengan bobot . Meskipun diisi dengan tiga metode P (jenis kelamin, jari, langit-langit), tetapi jika Anda mengisinya dengan data berdasarkan statistik OCR, Anda dapat secara signifikan meningkatkan kualitas pengenalan angka. Kode pustaka berisi file sumber daya NumeralLevenshteinData.txt, di mana Anda dapat memasukkan data dari tabel serupa menggunakan Ctrl + A, Ctrl + C dan Ctrl + V.

Jika karakter non-tabel ditemukan dalam teks, misalnya, nol, maka biaya memasukkannya sama dengan nilai maksimum dari tabel, dan biaya menghapus dan mengganti sama dengan minimum, sehingga algoritme lebih mungkin untuk mengganti nol dengan huruf "o", dan jika Anda menggunakan versi ketiga dari tesseract , maka masuk akal untuk menambahkan nol pada tabel dan menuliskan harga minimum untuk menggantinya dengan huruf "o".

Jadi, kami menyiapkan data untuk algoritma Wagner-Fisher, mari kita buat perubahan pada algoritma untuk memecah string menjadi token. Untuk melakukan ini, kami akan menjalani analisis tambahan dari setiap token, tetapi sebelum itu kami akan memperluas informasi tentang token dengan karakteristik berikut:

• Tingkat kesalahan Angka nyata dari 0 (tidak ada kesalahan) hingga 1 (token tidak benar), yang berarti seberapa baik token dibandingkan dengan sampel.
  
• Tanda menggunakan token . Saat mengurai string dengan puing-puing yang diselingi, sebagian token akan dibuang, karena atribut ini tidak akan ditetapkan. Dalam hal ini, nilai kesalahan total akan dianggap sebagai rata-rata aritmatika dari kesalahan token yang digunakan.
  

Algoritma Analisis Token:

1. Kami mencoba menemukan token di tabel apa adanya. Jika kami menemukan - semuanya baik-baik saja, kembalikan.
2. Jika tidak, buat daftar opsi yang memungkinkan:

3. Kami mencoba mencocokkan token dengan sampel menggunakan algoritma Wagner-Fisher. Opsi ini terdiri dari satu token (sampel dipetakan) dan kesalahannya sama dengan jarak terbaik dibagi dengan panjang sampel.

   
   Contoh: token "nol" dibandingkan dengan sampel "nol", sedangkan jaraknya 0,5, karena biaya penggantian huruf buruk "y" dengan "o" yang baik adalah 0,5. Total kesalahan untuk token ini adalah 0,5 / 4 = 0,125.
   

4. Jika substring cukup besar (saya punya 6 karakter), kami mencoba membaginya menjadi dua bagian dengan setidaknya 3 karakter di masing-masing. Untuk string 6 karakter akan ada satu divisi: 3 + 3 karakter. Untuk string 7 karakter - sudah ada dua opsi, 3 + 4 dan 4 + 3, dll. Untuk setiap opsi, kami memanggil fungsi analisis token yang sama secara rekursif, kami memasukkan opsi yang diterima ke dalam daftar.

   
   

   Agar tidak mati dalam rekursi, kami menentukan tingkat kegagalan maksimum. Selain itu, opsi yang diperoleh sebagai hasil pembagian secara artifisial terdegradasi dengan jumlah tertentu (opsi, secara default 0,1), sehingga opsi perbandingan langsung lebih bernilai. Saya harus menambahkan operasi ini, karena subteps dari tipe "ganda" berhasil dibagi menjadi token "dua" dan "lima", dan tidak dikurangi menjadi "dua puluh". Sayangnya, ini adalah fitur dari bahasa Rusia.

   
   

   Contoh: token "ganda" memiliki perbandingan langsung dengan sampel "dua puluh", kesalahan 0,25. Selain itu, opsi terbaik untuk membagi adalah "dua" + "lima" dengan biaya 0,25 (mengganti "a" dengan "i"), secara artifisial memburuk menjadi 0,35, akibatnya token "dua puluh" lebih disukai.

   
   
5. Setelah mengkompilasi semua opsi, kami memilih yang terbaik dengan jumlah kesalahan minimum yang berpartisipasi di dalamnya. Hasilnya dikembalikan.

Selain itu, verifikasi token dimasukkan ke dalam algoritma pembuatan nomor utama sehingga kesalahan mereka tidak melebihi nilai tertentu (opsi, default 0,67). Dengan ini, kami menyaring kemungkinan sampah, meskipun tidak terlalu berhasil.

Algoritma singkatnya bagi mereka yang terlalu malas untuk membaca teks di atas

Kami membagi string input, yang merupakan angka dalam kata, menjadi substring menggunakan \ s + keteraturan, lalu kami mencoba mencocokkan setiap substring dengan token sampel atau membaginya menjadi substring yang lebih kecil, memilih hasil terbaik. Sebagai hasilnya, kita mendapatkan satu set token dengan mana kita menghasilkan angka, dan nilai kesalahan diambil sebagai rata-rata aritmatika dari kesalahan di antara token yang digunakan dalam generasi.

Mempertajam suatu algoritma untuk tugas tertentu

Dalam tugas saya, angkanya non-negatif dan relatif kecil, jadi saya akan mengecualikan token yang tidak perlu dari "juta" dan lebih tinggi. Untuk ujian, pembaca yang budiman, sebaliknya, saya menambahkan token jargon tambahan, yang memungkinkan string parsing seperti "lima potong", "memotong dua ratus" dan bahkan "tiga stolnik dan dua keping emas". Ini lucu, tetapi bahkan tidak memerlukan perubahan pada algoritma.

Perbaikan lebih lanjut

Algoritma yang ada memiliki kekurangan:

1. Kontrol Kasus. String "dua ribu" dan "dua ribu" akan dikenali dengan nol kesalahan sebagai 2000. Dalam tugas saya, kontrol kasus tidak diperlukan, bahkan berbahaya, tetapi jika Anda memerlukan fungsi seperti itu, ini diselesaikan dengan memperkenalkan bendera tambahan dalam token yang bertanggung jawab untuk kasus token berikutnya. .
   
2. Angka negatif. Token minus tambahan diperkenalkan dengan pemrosesan khusus. Tidak ada yang rumit, tetapi jangan lupa bahwa huruf "y" buruk dan tidak muncul dalam angka, Anda perlu mengubah karakteristik bobotnya atau berharap tidak berubah selama proses OCR.
   
3. Angka pecahan. Ini diselesaikan dengan mengganti tipe panjang dengan token ganda dan memperkenalkan "persepuluh", "seperseratus", dll ... Jangan lupa untuk merevisi skala surat.
   
4. Pengakuan angka yang dimasukkan oleh pengguna. Karena saat memasukkan teks secara manual, kami paling sering membuat kesalahan yang berkaitan dengan mengedit ulang siVMolov, Anda harus menambahkan operasi ini ke algoritma Wagner-Fisher.
   
5. Dukungan untuk bahasa lain. Kami memperkenalkan token baru, memperluas tabel bobot.
   
6. Penanganan sampah. Dalam beberapa dokumen, data dicetak, kualitas gambar mungkin buruk, sel mungkin klise kosong. Dalam hal ini, sampah yang perlu dibersihkan entah bagaimana masuk ke jalur. Yang terbaik yang bisa saya tawarkan saat ini adalah melakukan pra-proses dokumen sebelum OCR. Menghapus garis-garis tabel dan mengisinya dengan warna yang dekat dengan warna ruang kosong sel banyak membantu saya. Ini tidak menyelesaikan semua masalah, tetapi meningkatkan kualitas pengenalan teks dari dokumen di mana tabel memiliki kelengkungan karena memar dokumen atau fotografer yang bengkok. Idealnya, Anda harus memutar sel itu sendiri dan mengenalinya secara terpisah, jika Anda, tentu saja, memiliki meja sama sekali.
   

Jadi apa intinya?

Proyek ini memiliki contoh aplikasi konsol yang berjalan melalui file samples.txt dengan contoh untuk parser. Berikut ini adalah screenshot dari hasilnya:

Saya menagih Anda untuk mengevaluasi hasilnya, tetapi bagi saya, itu tidak buruk. Kesalahan untuk contoh pengakuan nyata tidak melebihi 0,25, meskipun saya belum menjalankan seluruh set dokumen yang tersedia, mungkin tidak semuanya akan lancar di sana.

Adapun bagian terakhir, saya selalu bertanya-tanya berapa banyak ini "dofiga". Juga, program itu sendiri memberikan jawaban yang memadai untuk berapa banyak yang diperlukan (saya tidak menggunakan, tapi tetap saja) dan bahkan secara akurat menentukan arti dari kata lama Rusia "kegelapan." Dan ya, kesimpulannya belum termasuk ukuran lain bahwa pendidikan tidak diperbolehkan untuk menambahkan, tetapi program percaya bahwa itu sama dengan seribu =)

Beberapa kata tentang perpustakaan

Awalnya, rencana saya tidak termasuk pembuatan perpustakaan, saya memutuskan untuk mendesainnya secara eksklusif untuk Habr. Saya mencoba untuk meletakkan kode, tetapi jika Anda menggunakannya, buatlah garpu atau salinan kemungkinan besar Anda tidak perlu jargon dan token lain yang termasuk dalam contoh.

Pustaka itu sendiri ditulis di bawah .NET Standart 2.0 dan C # 7.x, dan algoritme mudah diterjemahkan ke bahasa lain.

Dalam hal kemungkinan perluasan perpustakaan, saya akan menambahkan komposisi komponen penting dari pengurai angka dalam kata-kata (Genesis.CV.NumberUtils namespace):

• RussianNumber.cs - langsung parser
• RussianNumber.Data.cs - file dengan deskripsi token
• RussianNumber.ToString.cs - konverter angka ke teks dalam kata-kata
• RussianNumberParserOptions.cs - opsi parser
• NumeralLevenshtein.cs - implementasi algoritma Wagner-Fisher
• NumeralLevenshteinData.txt - sumber daya, data bobot surat

Penggunaan:

• RussianNumber.ToString (value) - mengonversi angka menjadi teks
• RussianNumber.Parse (value, [options]) - mengonversi teks menjadi angka

Kesimpulan

Saya benar-benar berharap artikel itu tidak terasa membosankan bagi Anda meskipun ada banyak teks. Baru-baru ini, saya telah menemukan banyak topik yang berkaitan dengan visi komputer, tentang yang ada sesuatu untuk diceritakan, jadi saya ingin tahu pendapat tentang format artikel ini. Apa yang pantas ditambahkan atau, sebaliknya, dihilangkan? Apa yang lebih menarik bagi Anda, pembaca, algoritma itu sendiri atau fragmen kode?

Apakah Anda suka artikelnya? Lihat yang lain:

• Dukungan serialisasi JavaScript JavaScript
  
• Mengisi templat teks dengan data berbasis model. Implementasi .NET menggunakan fungsi bytecode dinamis (IL)