lafzi

README

Go-Lafzi

Go-Lafzi is a Go package for searching Arabic text using its transliteration (phonetic search).

It works by using indexed trigrams for approximate string matching, with search results ranked using heuristics such as compactness and completeness. For storing the indexes, it uses Modernc's port of SQLite database that does not rely on cgo. Thanks to this, we gain several advantages:

• Since it doesn't use cgo, it can be easily used across platforms.
• It can be safely used concurrently.
• It can be easily modified using various database editors.
• The lookup process is fast, as SQLite is efficient at reading data.

Features

• Transliteration search — queries like rahman, alhamdulillah, or ulul albab in any common Latin transliteration style. Ambiguous digraphs (dh, th, dz, dl, tz are used for different Arabic letters depending on the style) are searched in every plausible reading.
• Arabic queries — queries in Arabic script, with harakat (matched phonetically) or without harakat (matched against a consonant skeleton index).
• Undiacritized documents — documents without harakat (common in raw hadith corpora) can be indexed too; Latin and Arabic queries reach them through the consonant skeleton index, at a reduced confidence.
• Recitation-aware matching — hamzat wasl elision (bismillahir rahman, ulul albab) and sun-letter assimilation are handled, so queries can be written the way the text is recited.
• Morphological tolerance — a vowel-collapsed fallback index matches other forms of the same root (a dhaalliin query also finds the dhaalluun form), ranked below exact matches by a confidence penalty.
• Accurate positions — every result carries [start, end) rune ranges into the original Arabic string, suitable for highlighting, including letters that carry no phonetic value (tatweel, superscript alef, waqf marks).

The corpus does not have to be the Quran — any Arabic text collection works (hadith, prose, poetry). On the full Quran (6,236 ayah, 499 benchmark queries) the package reaches ~0.998 recall at ~8 ms per query, and indexes the whole corpus in a few seconds. Opening a storage preloads a small in-memory cache (~10 MB for the whole Quran) of the most common tokens.

Usage

For example, we want to find the word "rahman" within surah Al-Fatiha:

package main

import (
 "encoding/json"
 "fmt"
 "os"

 "github.com/ilhamsyahids/go-lafzi"
)

var arabicTexts = []string{
 "بِسْمِ اللَّهِ الرَّحْمَـٰنِ الرَّحِيمِ",
 "الْحَمْدُ لِلَّهِ رَبِّ الْعَالَمِينَ",
 "الرَّحْمَـٰنِ الرَّحِيمِ",
 "مَالِكِ يَوْمِ الدِّينِ",
 "إِيَّاكَ نَعْبُدُ وَإِيَّاكَ نَسْتَعِينُ",
 "اهْدِنَا الصِّرَاطَ الْمُسْتَقِيمَ",
 "صِرَاطَ الَّذِينَ أَنْعَمْتَ عَلَيْهِمْ غَيْرِ الْمَغْضُوبِ عَلَيْهِمْ وَلَا الضَّالِّينَ",
}

func main() {
 // Open storage
 for _, path := range []string{"sample.lafzi", "sample.lafzi-wal", "sample.lafzi-shm"} {
  os.RemoveAll(path)
 }
 storage, err := lafzi.OpenStorage("sample.lafzi")
 checkError(err)
 defer storage.Close()

 // Prepare documents
 var docs []lafzi.Document
 for i, arabicText := range arabicTexts {
  docs = append(docs, lafzi.Document{
   Identifier: fmt.Sprintf("%d", i+1),
   Arabic:     arabicText},
  )
 }

 // Save documents to storage
 err = storage.AddDocuments(docs...)
 checkError(err)

 // Search in storage
 results, err := storage.Search("rahman")
 checkError(err)

 // Print search result
 bt, _ := json.MarshalIndent(&results, "", "\t")
 fmt.Println(string(bt))
}

func checkError(err error) {
 if err != nil {
  panic(err)
 }
}

Which will give us following results :

[
 {
  "Identifier": "1",
  "Text": "بِسْمِ اللَّهِ الرَّحْمَـٰنِ الرَّحِيمِ",
  "Confidence": 1,
  "Positions": [[15, 27]]
 },
 {
  "Identifier": "3",
  "Text": "الرَّحْمَـٰنِ الرَّحِيمِ",
  "Confidence": 1,
  "Positions": [[0, 12]]
 }
]

Each entry in Positions is a [start, end) rune range into Text that can be used to highlight the match. The range covers the whole matched word, including its definite article.

Notes:

• The storage database uses SQLite in WAL mode, so it may create -wal and -shm sidecar files next to it. Call storage.Close() before the process exits to checkpoint them.
• Databases indexed by older versions of this package must be re-indexed (call AddDocuments again) to make use of the newer indexes for Arabic queries without harakat and morphological matching.
• Matching quality is best when documents are fully diacritized: without harakat only the consonant skeleton can match, which is less precise.

For more examples, check out the sample directory. It contains two examples:

• sample/simple is a sample project demonstrating the basic usage described above.
• sample/quran is a sample project that indexes the entire Quran and runs a recall benchmark against 499 transliterated queries.

Resources

The original PDF copies of these papers can be found in the doc folder of the upstream repo.

By the way, the algorithm that implemented in this package is not exactly the same as in these papers. There are also some papers that I ignored, i.e. the papers to find Arabic text cross-verse in Qur'an, which I believe not really useful for general Arabic texts. There are also many parts that I've changed to make implementation easier and to increase performance in testing.

• Istiadi, Muhammad Abrar. "Sistem pencarian ayat al-quran berbasis kemiripan fonetis." (2012).
• Zafran, Aidil, Moch Arif Bijaksana, and Kemas M. Lhaksmana. "Truncated query of phonetic search for al qur’an." 2019 7th International Conference on Information and Communication Technology (ICoICT). IEEE, 2019. (Link Paper)
• Rifaldi, Eki, Moch Arif Bijaksana, and Kemas Muslim Lhaksamana. "Sistem Pencarian Lintas Ayat Al-Qur'an Berdasarkan Kesamaan Fonetis." Indonesia Journal on Computing (Indo-JC) 4.2 (2019): 177-188. (Link Paper)
• Rasyad, Naufal, Moch Arif Bijaksana, and Kemas Muslim Lhaksmana. "Pencarian Potongan Ayat Al-Qur'an dengan Perbedaan Bunyi pada Tanda Berhenti Berdasarkan Kemiripan Fonetis." Jurnal Linguistik Komputasional 2.2 (2019): 56-61.
• Satriady, Wildhan, Moch Arif Bijaksana, and Kemas M. Lhaksmana. "Quranic Latin Query Correction as a Search Suggestion." Procedia Computer Science 157 (2019): 183-190. (Link Paper)
• Octavia, Agni, Moch Arif Bijaksana, and Kemas Muslim Lhaksmana. "Verse Search System for Sound Differences in the Qur’an Based on the Text of Phonetic Similarities." Jurnal Sisfokom (Sistem Informasi dan Komputer) 9.3 (2020): 317-322. (Link Paper)
• Fitriani, Intan Khairunnisa, Moch Arif Bijaksana, and Kemas Muslim Lhaksmana. "Qur’an Search System for Handling Cross Verse Based on Phonetic Similarity." Jurnal Sisfokom (Sistem Informasi dan Komputer) 10.1 (2021): 46-51. (Link Paper)
• Purwita, Naila Iffah, et al. "Typo handling in searching of Quran verse based on phonetic similarities." Register: Jurnal Ilmiah Teknologi Sistem Informasi 6.2 (2020): 130-140. (Link Paper)
• Cendikia, Putri, Moch Arif Bijaksana, and Kemas M. Lhaksmana. "Pencarian Ayat Al-Qur'an Yang Tidak Utuh Berdasarkan Kemiripan Fonetis." eProceedings of Engineering 7.2 (2020). (Link Paper)
• Elder, Robert. "Myers Diff Algorithm - Code & Interactive Visualization." (2017) (Link Paper)

License

MIT

Documentation

Index

• type Document
• type Result
• type Storage
  • func OpenStorage(path string) (*Storage, error)
  • func (st *Storage) AddDocuments(docs ...Document) error
  • func (st *Storage) Close() error
  • func (st *Storage) DeleteDocuments(identifiers ...string) error
  • func (st *Storage) Search(query string) ([]Result, error)
  • func (st *Storage) SetMinConfidence(f float64)

Types

type Document

type Document struct {
	Identifier string
	Arabic     string
}

Document is the Arabic document that will be indexed.

type Result

type Result struct {
	Identifier string
	Text       string
	Confidence float64
	Positions  [][2]int
}

Result contains id of the suitable document and its confidence level.

type Storage

type Storage struct {
	// contains filtered or unexported fields
}

Storage is the container for storing reverse indexes for Arabic documents that will be searched later. Use sqlite3 as database engine.

func OpenStorage

func OpenStorage(path string) (*Storage, error)

OpenStorage open the reverse indexes database in the specified path.

func (*Storage) AddDocuments

func (st *Storage) AddDocuments(docs ...Document) error

AddDocuments save and index the documents into the storage.

func (*Storage) Close

func (st *Storage) Close() error

Close closes the storage. This checkpoints the write-ahead log, so it should always be called before the process exits.

func (*Storage) DeleteDocuments

func (st *Storage) DeleteDocuments(identifiers ...string) error

DeleteDocuments remove the documents in the storage.

func (*Storage) Search

func (st *Storage) Search(query string) ([]Result, error)

Search for suitable documents using the specified query. The query can be either a Latin transliteration or Arabic text. Arabic queries without harakat are matched against the consonant skeleton of the documents.

func (*Storage) SetMinConfidence

func (st *Storage) SetMinConfidence(f float64)

SetMinConfidence set the minimum confidence score for the search result, clamped between 0 and 1. Default is 40%. Setting it to 0 disables the confidence filter entirely.