Extracting the roots of Arabic words without removing affixes

Abstract

Most research in Arabic roots extraction focuses on removing affixes from Arabic words. This process adds processing overhead and may remove non-affix letters, which leads to the extraction of incorrect roots. This paper advises a new approach to dealing with this issue by introducing a new algorithm for extracting Arabic words’ roots. The proposed algorithm, which is called the Word Substring Stemming Algorithm, does not remove affixes during the extraction process. Rather, it is based on producing the set of all substrings of an Arabic word, and uses the Arabic roots file, the Arabic patterns file and a concrete set of rules to extract correct roots from substrings. The experiments have shown that the proposed approach is competitive and its accuracy is 83.9%, Furthermore, its accuracy can be enhanced more in the sense that, for about 9.9% of the tested words, the WSS algorithm retrieves two candidates (in most cases) for the correct root.

Keywords

Arabic roots information retrieval search engines stemming

1. Introduction

In this era of the internet and with the extensive number of documents that are posted every single minute, extracting relevant documents is getting more difficult. Therefore, extracting the roots of words (or stemming), which is used to facilitate retrieving relevant documents, has become an important issue. Stemming is a major part of many applications, such as data compression, spelling checkers, text summarization and machine translation. Moreover, word-roots are used to extend queries to retrieve the most relevant information with higher recall and precision.

In some languages, such as English, stemming is an easy process since it can be performed by removing suffixes. In Arabic, however, extracting roots is a difficult and a complicated issue owing to the fact that Arabic has a rich and complex morphology. An Arabic word may have prefixes, infixes and suffixes. Furthermore, some Arabic words may consist of only one or two letters, such as the words (عـِ) and (قُل), where both have omitted root letters. In addition, affixes consist of different numbers of characters.

Arabic words have a sophisticated morphology; they can be built using roots and patterns, where patterns can be described as templates with grammatical rules. A template can be represented as a combination of the root (فعل F’al) and a set of prefixes, infixes or suffixes. For example, the template (فاعل fa′ael) is a combination of the root (فعل f′al) and the infix (ا a). An Arabic word can be constructed by replacing the letters of the root (فعل f′al) in an appropriate template with the letters of the root for the word to be constructed. For example, to construct the word ‘scientist’ (عالم′aalem) in Arabic, we should use the pattern (فاعل fa′ael) and replace the letters of (فعل f′al) with the letters of the root (علم ′alem) and keep the infix (ا a).

Most researchers have focused on reversing the process discussed in the previous paragraph by removing affixes to obtain the correct root. However, the aforementioned process is not easy and may remove original letters (non-affix letters) during the filtering process, which may produce incorrect roots. This paper deals with the problem from a different angle by extracting word roots without removing affixes. The paper introduces a new algorithm called Word Substring Stemming (WSS), which works based on the fact that an Arabic word consists of its root’s letters separated by affixes (with some exceptions discussed in Section 3.2.2). The algorithm extracts all substrings of a given word and uses Arabic roots file and patterns file التصاريف) tasareef) to choose the correct root from the substrings. We should mention here that most Arabic roots consist of three (trilateral) or four letters (quadric) [1]. Therefore, this paper deals with extracting only those roots and does not consider other types.

The rest of the paper is organized as follows. The next section introduces some related work. Section 3 demonstrates the WSS algorithm. The experiments and results are discussed in Section 4. Finally, Section 5 presents the conclusion and future work.

2. Related work

The retrieval of documents in Arabic language has become a significant issue owing to the continuous evolution of the Internet and the huge spread of Arabic documents. Extensive work has been performed to enhance the precision of retrieving relevant documents by constructing good Arabic stemmers. Some researchers developed stemmers by removing some prefixes and/or suffixes without dealing with infixes [2 –4]. Taghva et al. [3] developed a stemmer that is based on matching patterns and removing prefixes and suffixes to extract the root. To enhance the matching process, they used a set of diacritical marks, affixes and patterns. Similarly, Momani and Faraj [4] developed a stemmer based on prefix and suffix removal. The proposed stemmer sorts the term letters and removes double letters that belong to the set of extra characters, which consists of the following letters {س, أ, ل, ت, م, و, ن, ي, ه, ا} . The removing process continues until only three letters remain. However, the method of extracting roots by removing a fixed set of prefixes and suffixes suffers from some problems, such as the inability to distinguish between extra letters and root letters [5]. In a more interesting work, Khoja and Garside’s algorithm [6] removes affixes and uses pattern matching to extract roots; however, it has problems when dealing with nouns.

Word-pattern matching techniques were used in extracting Arabic roots [7 –9]. Based on this idea, a root is extracted after removing the affixes attached to the given word. The root extraction is performed by matching the positions of the word letters with the corresponding pattern. Al-Fedaghi and A1-Anzi [9] developed a stemmer that matches each word with all possible patterns that have the same length of letters. Then, the stemmer extracts the trilateral substring in the positions (ف f), (ع ′a), and (ل L). The retrieved substring is considered the root of the word if the retrieved substring exists in the roots’ file.

N-gram systems [10] and clustering methods [11] are also used to extract Arabic roots. Rogati et al. [12] presented an unsupervised learning approach to build an Arabic stemmer. They used a statistical machine translation approach that learns to retrieve the prefix, stem and suffix of a word using a training set. Harmanani et al. [13] proposed a rule-based stemmer for Arabic information retrieval. Their algorithm uses a rule engine that extracts stems based on a set of language-dependent rules. Chen and Gey [14] clustered Arabic words into stem classes using their mappings to English stem classes. They performed this process based on a parallel English–Arabic corpus and an English stemmer. Kadri et al. [15] developed a stemmer that extract roots according to linguistic rules.

Boudlal et al. [16] used an approach based on hidden Markov models and claimed that this model can achieve very good precision in extracting Arabic roots. Al-Nashashibi et al. [17] introduced some corrections or enhancements such as replacing long vowels and handling specific cases of hamzated words, which can be used in existing algorithms to improve their performance. They showed that using the corrections in the light stemmer proposed by Al-Ameed [18] can improve its performance by about 14%. Hmeidi et al. [19] proposed an algorithm that is based on bigrams. They used two similarity measures – Manhatten distance and Dice’s measure – to test the algorithm’s accuracy, which was claimed to be 86% for trilateral roots.

Al-Kabi and Al-Mustafa [20] proposed an algorithm that is based on affixes removal and the knowledge extracted from structural linguistics. However, the level of complexity of the algorithm is high, and its accuracy depends on the arranging of root patterns. Similarly, Al-Sarhan et al. [21] introduced a new algorithm that is based on Arabic root patterns. Nonetheless, their algorithm assigns numeric values to listed letters and uses those values in roots extraction. Ghawanmeh et al. [22] suggested an algorithm based on Arabic root patterns; however, they used only 81 patterns in the extraction process, which reduces the time needed for extracting Arabic roots.

Most of the aforementioned approaches focused on removing the affixes of a word to extract its root. However, these approaches suffer from the problem of distinguishing between the letters of affixes and the letters of roots. Moreover, they add processing overhead that may not be acceptable in some systems. This paper introduces a new approach that deals with the stemming problem from a different angle by eliminating the need to remove affixes in root extraction. This has an advantage of the elimination of the uncertainty resulting from the distinction between the affix letters and the root letters. It also does not add any processing and computations overhead.

3. The WSS-based algorithm

The proposed approach consists of two phases, which are the pre-processing of words and extracting roots. This section introduces the WSS algorithm and explains its phases in details.

3.1. Preparing the word (pre-processing)

Before using the WSS algorithm to extract a word’s root, the word is prepared by removing letters that are highly probably not the root’s letters. We should mention here that this phase is simple and does not aim to remove affixes. Strictly speaking, it aims to reduce the number of substrings of a word used in the WSS algorithm, and to enhance the probability of finding the correct root. In this phase, the following letters are removed before using the algorithm:

The letters (ال Al) (ال التعريف), such as in the word العلم (al′elm Science). The (ال Al) is a particle (harf) that is always used to render the noun on which it is prefixed definite. That is, it is not part of roots and should be eliminated from any word.

The letter (ة t) at the end of the word, such as in the word خزانة (khazanat Locker). The letter (ة t) is used in Arabic to distinguish the word either as male or as female, therefore, it should be eliminated.

The letters (ات at) at the end of the word, such as the word ملاحظات (molahazat Notes). They are used in Arabic to indicate plurals.

One of the doubled letters at the beginning of a word, such as the letter (ب b) in the word بباب (bebab At the Door). This is a preposition in Arabic and means in.

The second weak letter when there are two successive weak letters in a word, such as the letter (ا a) in the word واجب (wajeb Duty ). In Arabic, if any two weak letters comes one after another, then the second letter is considered as extra and should be eliminated because it will not be part of the root.

In addition, the preparation process converts some letters to their original forms, such as converting ئ to آ, ؤ, to أ, and ى into ي. This process is performed since Arabic roots contain the letters {ئ, آ, ى} in their original forms only. Moreover, if the word consists of one letter only such as the word عِ(′ae Realize), the letters (و O) and ( ي Y) are added to the end and to the beginning, respectively. For example, (عِ ′ae) becomes وعي (wa′aya Realization). This type of words exists when transforming some words into the (صيغة أمر) in which the weak letters (ي, و, ا} (أحرف العلة) are omitted. In other words, without loss of generality, when a word consists of one letter only, it means that it misses the letter و at the beginning and the letter ي at the end. Therefore, they should be added before using the algorithm.

3.2. The WSS algorithm

The WSS algorithm is used to extract both trilateral and quadric roots. Basically, the algorithm extracts all syntactically correct substrings from the given word, where a substring is defined as follows:

Definition 1. Given a word W that consists of a set of ordered letters from right to left K = {k₁, k₂, …, k_n}, A subset B = {k_i, k_i _{+ 1}, …, k_l} is a substring of W iff B ⫅ K ∧ (∀k_i∀k_j position(k_i) < position(k_j) in B → position(k_i) < position(k_j) in W).

The algorithm assumes that the correct root of a word is highly probably found among the retrieved substrings. Therefore, it uses the roots file, the patterns file (التصاريف tasareef) and some rules to pick the correct root. Algorithm 1 (WSS algorithm) shows the complete process of extracting the roots of Arabic words. Before discussing the algorithm, let us define the Set of Extra Letters (أحرف الزيادة), and the set of Weak Letters (أحرف العلة).

Definition 2. Given an Arabic word W that consists of a set of ordered letters from right to left W = {W₁,W₂, …, W_n}. If a letter L ∈ W is not a root letter, L is called an extra letter (affix letter), and the set of letters that may exist as affixes letter, which is the set {سـألتمونيها) {ا ه ي ن و م ت ل أ س sa′ltmonyha), is called the set of extra letters.

Definition 3. Consider the vowels in English language; Arabic letters that have similar properties to the vowels in English language are called weak letters, which are ا (alif), و (waw), and ي (ya’).

Algorithm 1. WSS algorithm
Input : An Arabic word W, an empty set of candidate roots CR, an empty set of substrings S, Quadric Root File QRF, Trilateral Root File TRF, Patterns File PF, an empty set of Correct Roots RR. Output : The root of W. Method : Apply the following steps in order to get the root. In the third and fourth steps, apply the steps in order. If a step succeeds in extracting the root, retrieve the root and exit the algorithm. 1. Prepare W // i.e. remove … ال, ات 2. Extract all trilateral and quadric substrings from W. 3. For each substring G 4. CHECKSPELLING(G) //Check the spelling of G (using VBA(visual basic for applications)) 5. If SPELLING(G) = TRUE //Pick the (syntactically) correct substrings as substrings candidates 6. S ← S ∪ {G} //store G in the set S. 7. Search of quadric root (QR) candidates using the following rules. 8. If ∃G∈S ∧ QR(G) ∧ (EXTRA(G) =0)//Search for a quadric substring(s)(QR) in S that has no extra letters 9. CR ← CR ∪ {G} //store G in the set of root candidates CR. 10. Else If ∃G∈S ∧ QR(G) ∧ (EXTRA(G) =1) //Search for a QR in S that has one extra letter 11. CR ← CR ∪ {G} //store G in the set of root candidates CR. 12. Else If ∃G∈S ∧ QR(G) ∧ (EXTRA(G) = 2) //Search for a QR in S that has two extra letter 13. CR ← CR ∪ {G} //store G in the set of root candidates CR. 14. Else If ∃G∈S ∧ QR(G) ∧ (EXTRA(G) = 3) //Search for a QR in S that has three extra letter 15. CR ← CR ∪ {G} //store G in the set of root candidates CR. 16. Else If ∃G∈S ∧ QR(G) ∧ (EXTRA(G) = 4) //Search for a QR in S that has four extra letter 17. CR ← CR ∪ {G} //store G in the set of root candidates CR. 18. If LENGTH(CR) = 0 // no quadric root exists 19. Go to Step 33 20. Else If LENGTH(CR) >= 1//CR contains one or more root candidates 21. For each G ∈ CR 22. If CONTIGUOUS(G,W) ∧ G ∈ QRF //Choose G that is contiguous in W and exists in quadric root file 23. Root ← Root ∪ {G} 24. If LENGTH(Root) = 0 // steps 21–23 failed to find a root 25. W′ ← W – {ا,و,ي} //remove the weak letters from W to form a new word W′ 26. For each G ∈ CR 27. If CONTIGUOUS(G,W′)∧G ∈ QRF//Choose G that is contiguous in W′ and exists in quadric root file 28. Root ← Root ∪ {G} 29. If LENGTH(Root) = 0 // steps 24–28 failed to find a root 30. For each G ∈ CR 31. If G ∈ QRF//Choose G that exists in quadric root file 32. Root ← Root ∪ {G} 33.If LENGTH(Root) = 0 //If No Quadric root exists, search for a trilateral root TR using the following rules 34. Length(CR)0 //empty CR for a new round 35.Search for trilateral root (TR) candidates using the following rules: 36.If ∃G ∈S ∧ TR(G) ∧ (EXTRA(G) =0)//a trilateral substring(s)(TR) in S that has no extra letter 37. CR ← CR ∪ {G} //store G in the set of root candidates CR. 38.Else If ∃G∈S ∧ TR(G) ∧ (EXTRA(G) =1) //a trilateral substring(s)(TR) in S that has one extra letters 39. CR ← CR ∪ {G} //store G in the set of root candidates CR. 40.Else If ∃G∈S ∧ TR(G) ∧ (EXTRA(G) = 2)//a trilateral substring(s)(TR) in S that has two extra letters 41. CR ← CR ∪ {G} //store G in the set of root candidates CR. 42.Else If ∃G∈S ∧ TR(G) ∧ (EXTRA(G) = 3) //a trilateral substring(s)(TR) in S that has three extra letters 43. CR ← CR ∪ {G} //store G in the set of root candidates CR. 44.If LENGTH(CR) = 1//if one candidate root exist, retrieve it as the root 45. Root ← CR 46.Else If LENGTH(CR) > 1//CR contains more than one root candidates 47. For each G ∈ CR 48. If (G ∉ TRF) //if G is not in the trilateral roots file 49. CR ← CR – {G} //Remove G from CR 50. If LENGTH(CR) = 1 //if one candidate root exist, retrieve it as the root 51. Root ← CR 52. Else If LENGTH(CR) > 1 53. For each G ∈ CR 54. For each P ∈ PF //for each pattern in patterns file (فعل،مفاعل، فعول …} (التصاريف} 55. NP ← P(G)/produce the pattern of G by replacing the letters ل ع ف in P by the letters of G respectively 56. If NP = W //if the produced pattern is the same as W, add G to a new set RR 57. RR ← RR ∪ {G} 58. If LENGTH(RR) = 1//one root 59. Root ← RR //if RR contains one root, retrieve it as the root of W. 60. Else If LENGTH(RR) > 1 //more than one candidate root 61. For each K ∈ RR ∧ Contiguous(K,W) //Choose K that has contiguous letters in W as root 62. Root ← Root ∪ {K} 63. If LENGTH(Root) = 0 //steps 61–62 failed to find a root 64. For each K∈ RR ∧ Contiguous(K,W′) //where W′=W–infixes({ا,و,ي}), Choose K that is contiguous in W′ 65. Root ← Root ∪ {K} 66. If LENGTH(Root) = 0 //steps 64–65 failed to find a root 67. Root ← RR //Retrieve the substring(s) in RR as root(s). 68. If LENGTH(root) = 0 //fails to retrieve a root after using patterns file PF 69. Retrieve CR in step 49 as the set of root candidates for W

Algorithm 1. WSS algorithm

Input : An Arabic word W, an empty set of candidate roots CR, an empty set of substrings S, Quadric Root File QRF, Trilateral Root File TRF, Patterns File PF, an empty set of Correct Roots RR.
Output : The root of W.
Method : Apply the following steps in order to get the root. In the third and fourth steps, apply the steps in order. If a step succeeds in extracting the root, retrieve the root and exit the algorithm.
1. Prepare W // i.e. remove … ال, ات
2. Extract all trilateral and quadric substrings from W.
3. For each substring G
4. CHECKSPELLING(G) //Check the spelling of G (using VBA(visual basic for applications))
5. If SPELLING(G) = TRUE //Pick the (syntactically) correct substrings as substrings candidates
6. S ← S ∪ {G} //store G in the set S.
7. Search of quadric root (QR) candidates using the following rules.
8. If ∃G∈S ∧ QR(G) ∧ (EXTRA(G) =0)//Search for a quadric substring(s)(QR) in S that has no extra letters
9. CR ← CR ∪ {G} //store G in the set of root candidates CR.
10. Else If ∃G∈S ∧ QR(G) ∧ (EXTRA(G) =1) //Search for a QR in S that has one extra letter
11. CR ← CR ∪ {G} //store G in the set of root candidates CR.
12. Else If ∃G∈S ∧ QR(G) ∧ (EXTRA(G) = 2) //Search for a QR in S that has two extra letter
13. CR ← CR ∪ {G} //store G in the set of root candidates CR.
14. Else If ∃G∈S ∧ QR(G) ∧ (EXTRA(G) = 3) //Search for a QR in S that has three extra letter
15. CR ← CR ∪ {G} //store G in the set of root candidates CR.
16. Else If ∃G∈S ∧ QR(G) ∧ (EXTRA(G) = 4) //Search for a QR in S that has four extra letter
17. CR ← CR ∪ {G} //store G in the set of root candidates CR.
18. If LENGTH(CR) = 0 // no quadric root exists
19. Go to Step 33
20. Else If LENGTH(CR) >= 1//CR contains one or more root candidates
21. For each G ∈ CR
22. If CONTIGUOUS(G,W) ∧ G ∈ QRF //Choose G that is contiguous in W and exists in quadric root file
23. Root ← Root ∪ {G}
24. If LENGTH(Root) = 0 // steps 21–23 failed to find a root
25. W′ ← W – {ا,و,ي} //remove the weak letters from W to form a new word W′
26. For each G ∈ CR
27. If CONTIGUOUS(G,W′)∧G ∈ QRF//Choose G that is contiguous in W′ and exists in quadric root file
28. Root ← Root ∪ {G}
29. If LENGTH(Root) = 0 // steps 24–28 failed to find a root
30. For each G ∈ CR
31. If G ∈ QRF//Choose G that exists in quadric root file
32. Root ← Root ∪ {G}
33.If LENGTH(Root) = 0 //If No Quadric root exists, search for a trilateral root TR using the following rules
34. Length(CR)0 //empty CR for a new round
35.Search for trilateral root (TR) candidates using the following rules:
36.If ∃G ∈S ∧ TR(G) ∧ (EXTRA(G) =0)//a trilateral substring(s)(TR) in S that has no extra letter
37. CR ← CR ∪ {G} //store G in the set of root candidates CR.
38.Else If ∃G∈S ∧ TR(G) ∧ (EXTRA(G) =1) //a trilateral substring(s)(TR) in S that has one extra letters
39. CR ← CR ∪ {G} //store G in the set of root candidates CR.
40.Else If ∃G∈S ∧ TR(G) ∧ (EXTRA(G) = 2)//a trilateral substring(s)(TR) in S that has two extra letters
41. CR ← CR ∪ {G} //store G in the set of root candidates CR.
42.Else If ∃G∈S ∧ TR(G) ∧ (EXTRA(G) = 3) //a trilateral substring(s)(TR) in S that has three extra letters
43. CR ← CR ∪ {G} //store G in the set of root candidates CR.
44.If LENGTH(CR) = 1//if one candidate root exist, retrieve it as the root
45. Root ← CR
46.Else If LENGTH(CR) > 1//CR contains more than one root candidates
47. For each G ∈ CR
48. If (G ∉ TRF) //if G is not in the trilateral roots file
49. CR ← CR – {G} //Remove G from CR
50. If LENGTH(CR) = 1 //if one candidate root exist, retrieve it as the root
51. Root ← CR
52. Else If LENGTH(CR) > 1
53. For each G ∈ CR
54. For each P ∈ PF //for each pattern in patterns file (فعل،مفاعل، فعول …} (التصاريف}
55. NP ← P(G)/produce the pattern of G by replacing the letters ل ع ف in P by the letters of G respectively
56. If NP = W //if the produced pattern is the same as W, add G to a new set RR
57. RR ← RR ∪ {G}
58. If LENGTH(RR) = 1//one root
59. Root ← RR //if RR contains one root, retrieve it as the root of W.
60. Else If LENGTH(RR) > 1 //more than one candidate root
61. For each K ∈ RR ∧ Contiguous(K,W) //Choose K that has contiguous letters in W as root
62. Root ← Root ∪ {K}
63. If LENGTH(Root) = 0 //steps 61–62 failed to find a root
64. For each K∈ RR ∧ Contiguous(K,W′) //where W′=W–infixes({ا,و,ي}), Choose K that is contiguous in W′
65. Root ← Root ∪ {K}
66. If LENGTH(Root) = 0 //steps 64–65 failed to find a root
67. Root ← RR //Retrieve the substring(s) in RR as root(s).
68. If LENGTH(root) = 0 //fails to retrieve a root after using patterns file PF
69. Retrieve CR in step 49 as the set of root candidates for W

3.2.1. Analysis

The algorithm starts by preparing the given word as discussed in Section 3.1. Next, in step 2, it extracts all quadric and trilateral substrings of the word. In steps 3–6, the algorithm keeps valid (syntactically correct) substrings only. After this step, it searches for a quadric root. The algorithm searches for valid quadric substrings that have no extra letters as shown in steps 8–9. It assumes that, if such a substring exists, it is most probably a root candidate; therefore, the algorithm adds the substring to the set of root candidates (CR). If there is no substring with all letters original (has no extra letters), the algorithm searches for a substring that has the minimum number of extra letters and adds it to the set of root candidates (as shown in steps 10–17). The algorithm assumes that original letters in a word have very high probability of being root letters. This process is logical since other letters could be extra as it is purposely called ‘extra letters’, which are letters (affixes) that are added to roots to form various Arabic language words. Extra letters may exist as root letters too; meanwhile, original letters do not exist in a word as extra letters. After finishing this phase, the algorithm checks the set of retrieved root candidates (CR). If the algorithm fails to find a four-letter root candidate (step 18), the algorithm jumps to step 33 to search for a trilateral root. If there are quadric root candidates, the algorithm checks CR and searches for a root candidate that exists in the file of four-letter roots, and its letters are contiguous in the given word (W). If such candidate exists, it retrieves it as the root of W (steps 20–23). The algorithm assumes that the letters of the root of a word are highly probably contiguous in the word or separated by weak letters. Thus, if there is no candidate contiguous in W, the algorithm searches for a candidate that is separated by weak letters (as infixes) (steps 24–25). Notice that the algorithm checks the retrieved root candidate against the quadric roots file to ensure that it is a root.

If no quadric roots exist (step 33), the algorithm searches for a trilateral root. As performed in the searching process for a quadric root, the algorithm searches for a trilateral substring(s) that has the least extra letters (36–43) and adds it to the set of root candidates (CR). After these steps, if there is one three-letter root candidate only, the algorithm retrieves it as the root of the given word (steps 44–45). However, if there is more than one trilateral root candidate, the algorithm uses the trilateral roots file (TRF) to filter CR and removes any root candidate that does not exist in the TRF (steps 46–49). After the filtering process, if only one root candidate remains in CR, the algorithm retrieves it as the root of the given word (W) (steps 50-51). Otherwise, the algorithm uses the patterns file PF (التصاريف) to retrieve the correct root among the remaining root candidates. This process is performed by converting each root candidate in CR to each possible pattern in PF and produce new words. If a new word is the same as the given word (W), the corresponding root candidate is added to a new set called RR (steps 53–57). The converting process is performed by replacing the letters (ع ل ف f ′a l) in a pattern by the letters of the root candidate in order from right to left. For example, to convert the candidate root ثور (thawar Revolve) to the pattern (فعليون f′alyoon), we replace ف by ع, ث by و, and ل by ر, which produces the word ثوريون (thawryoon Revolutionists). If the new word ثوريون is the same as the given word W of which the algorithm is trying to find the root, the root candidate ثور is most probably the root of ثوريون and is added to the set RR. In the aforementioned example, the word ثوريون contains the root candidates ثور and (ثري tharya), and both root candidates exist in the trilateral roots file. However, when converting both root candidates using the patterns file, only ثور can be converted to the word ثوريون, which is produced using the pattern فعليون.

After finishing the process of converting root candidates to patterns, if there is one root candidate in RR, the algorithm retrieves it as the root of W (steps 58–59). Otherwise, the algorithm prefers the root candidate that is contiguous in W and retrieves it as the root (61–62). If there is no contiguous root candidate in W, the algorithm prefers the one that is separated by weak letters (as infixes) (64–65). If the previous steps fail, the algorithm retrieves all root candidates in RR as potential roots for W (65–66). This behaviour is based on the fact that Arabic words may have no infixes such as the word ثوريون. Thus, the algorithm assumes first that there are no infixes in the given word, and chooses a root candidate that is contiguous in the given word. If it fails, it assumes that the word contains weak letters (as infixes) which separate the letters of the correct root. Therefore, the algorithm removes the weak letters, and then it searches for a root candidate that is contiguous in the new word (without infixes weak letters). Steps 68–69 are stated owing to the probability that not all patterns exist in the patterns file PF. Thus, when the algorithm fails to retrieve one correct root from a set of candidates, it retrieves the entire set. We should mention here that steps 60–69 are rarely executed since after converting root candidates using the patterns file, the correct root is highly probably retrieved.

Figure 1 shows how the algorithm extracts the root of the word منبع (manb′a Source). As shown, the algorithm extracts the four-letter substrings of منبع (manb′a), which is منبع (step 2). Next, it checks the spelling of this substring and keeps it since it is syntactically correct (steps 3–6). Since منبع is the only four-letter substring, the algorithm adds it to the set of four-letter root candidates (steps 12–13). However, منبع is excluded by steps 22–23 because it does not exist in the four-letter roots file QRF. Since it does not exist in the roots file, the algorithm starts searching for a three-letter root. The correct three-letter substrings of منبع are منع (man′a Prevents) and نبع (nab′a Source) (steps 2–6). However, since نبع contains one extra letter ن (n), and منع contains two extra letters ن (n) and م (m), the algorithm adds نبع only to the set of root candidates (steps 38–39). Next, because نبع is the only root candidate, the algorithm retrieves it as the root of منبع (steps 44–45).

Figure 1.

Extracting the root of منبع.

More examples are demonstrated in Figure 2, which shows how to use the algorithm to extract the roots of the words المتدحرج (Almotadahrej Rolling) and {المواش (Almawashi The Livestock). The symbol ‘S X’ or ‘S X–Y’ on an output box indicates the step(s) that are used to generate the output, where S is an abbreviation to ‘Step’ and X or Y represents a step number. Note that, in the process of extracting the root of المواشي, the algorithm reaches a point where the substrings مشي (mashya Walked) and وشي (washya Tattle) are root candidates even after using the patterns file, where مشي is converted to مواشي (mawashya Livestock) using the pattern فواعل (fwa′ael), and وشي is converted to the same word using the pattern مفاعل (mafa’ael). Although it is uncommon case, the algorithm needs to deal with it. As shown in the figure, the algorithm prefers the root candidate that is contiguous in the filtered word (without weak letters as infixes), which is مشي, since there is no root candidate contiguous in the original word. Notice that وشي is not contiguous in the filtered word.

Figure 2.

Extracting the root of the words المتدحرج and المواشي.

3.2.2. Special cases

Some Arabic words cannot be manipulated using the mentioned rules in the algorithm such as the words that do not contain one of their root’s letters like جهة (Jehat Direction), مدّ (Madda Stretched), شدّ (Shadda Tightened) and لغة (Loghat Language) and the words that contain one letter only, like (عِ (′aey Realize), قِ (qey Protect)). These cases are manipulated using additional rules, which are not mentioned in the algorithm for simplicity.

After the preparation process, if the length of a word is less than three letters, the algorithm assumes that the word is a special case, and uses additional rules to extract the root of the word. In the case of the word that does not contain one of its root letters, the word letters are doubled one by one. After doubling a letter, the spelling of the produced word is checked. If it is syntactically correct, the algorithm is used to extract its root. If there is no valid root or there is no valid new word after doubling a letter of the given word, a letter و (w) or ي (y) is added to the beginning or to the end of the word, and the spelling is checked at each time. Then, the algorithm is used to extract the root of the new word. For instance, the letter د (d) is doubled in the word مدّ (madda) to produce the new word مدد (madada). Then, using the algorithm, the root of this word is مدد, which is correct. In the case of words like لغة (loghat), the letter ة (t) is removed in the preparation process. Doubling one of its letters fails in finding the correct root. Meanwhile, when the letter و (w) is added to the end of the word, a new word is produced, which is لغو (laghawa). Again, using the algorithm, the root of the new word is لغو, which is correct. The same thing is used for the word يصل (yasel arrive). The first letter ي (y) is removed in the preparation process and the letter و (w) is added to the beginning to produce the word وصل (wasal arrived), which is extracted as the root. In case of words that contain one letter only, the letter و (w) is added to the beginning of the word and the letter ي (y) is added to the end of the word. Then, the new word is considered as the root. For instance, the word عِ (′aey) is converted to the word وعي (w′aya), which is the correct root.

4. Experiments and results

The implementation was performed using Visual Basic for Applications (VBA) in Microsoft Word. The spelling checker in VBA in MS Word was used to check the correctness of the substrings of a word. The paper used the Holy Quran, which is the holy book in the Islamic religion, as the dataset to test the precision of the WSS algorithm. The Quran is written in Arabic language, and it contains 87,025 words, including stop words. The Quran text was filtered prior the testing process by removing all diacritics and stop words such as من (mena), على (‘ala), etc.

Figure 3 shows the accuracy of the WSS algorithm. To calculate the accuracy, a file that contains Arabic words and their correct roots was created. The file was prepared using an Arabic dictionary (Lesan Alarab لسان العرب). The accuracy was computed by comparing the roots extracted by the WSS algorithm with the correct roots in the file. As shown in Figure 3, the proposed algorithm retrieves the correct roots for 83.9% of the tested words. Moreover, it shows that the algorithm retrieves more than one root candidate for 9.9% of the tested words. That is, when the algorithm fails to retrieve one correct root in some cases, it retrieves more than one root candidate (two candidates in most cases), indicating that the root is among these candidates, but the algorithm cannot decide which one exactly. We should mention here that the words with multiple root candidates were not included in the computation of the accuracy. That is, they were considered as incorrect roots.

Figure 3.

The accuracy of the WSS algorithm.

Figure 4 shows the comparison between the accuracy of the WSS algorithm and five algorithms for Arabic roots extraction, which are Al-kabi [20] algorithm, Al-Sarhan [21] algorithm, Ghawanmeh algorithm [22], Taghva algorithm [3] and Hmeidi Algorithm [19]. A short description of these algorithms has been given in Section 2. The algorithms were tested using the words of the Quran as a dataset. As shown in Figure 4, the WSS approach has a competitive accuracy as it occupies rank 3 among the algorithms. Ghawanmeh’s stemmer occupies rank 1 as it achieves an accuracy of 95%, while Taghva’s stemmer has the least accuracy, about 38%. We should mention here that as there exist special cases that do not follow the rules of stemmers; a stemmer can be enhanced by addressing extra rules that deal with special cases similar to those handled in this paper in Section 3.2.2. That is, the accuracy of the aforementioned stemmers can be increased by dealing with special cases that cannot be dealt with using the stated rules. As a matter of fact, some strong stemmers fail to find the correct roots of words which are extracted correctly by some weak stemmers. Therefore, an enhanced stemmer can be built by combining the strength of two or more strong stemmers [23].

Figure 4.

A comparison between the accuracy of the WSS stemmer and the stemmers of Al-Kabi, Al-Sarhan, Ghawanmeh, Taghva and Hmeidi.

The Al-Kabi, Ghawanmeh, Taghva and Hmeidi algorithms are all based on affix removal. Normalizing words by removing affixes has a major flaw, which is the inability to differentiate between root and non-root (extra) letters in some cases; therefore, incorrect roots may be produced. For example, Ghawanmeh’s approach extracts the root فقي (Faqeya) for the word Horizontal (أفقية Ofoqeya), where the root is أفق (Afaqa). The approach considers the letter أ as a prefix. Similarly, Taghva’s approach extracts the root ولي (waleya) for the word Priority (أولوية Awlaweyah), where the correct root is أول (Awala). It considers the letter أ as a prefix, while, it is a root letter. Besides the probability of removing root letters, identifying and removing affixes poses extra processing overhead during root extraction. Unlike the aforementioned approaches, the WSS-based algorithm extracts roots without removing affixes. This feature eliminates the probability of removing roots letters during the extracting process, and reduces the time needed for root extraction.

Removing affixes is not performed in Al-Sarhan’s approach. It is based on assigning weights and ranks to the letters of words. Weights are real numbers in the range 0–5, which were determined by some experimentation on an Arabic text. After determining the weights of letters, the approach multiplies the rank of a letter (the order of a letter in a word) by its weight. Then, the three letters with the least product value are chosen as the three-letter root. Obviously, the efficiency of this approach depends on the correctness of the weights of letters and the formula it uses, which can be tested by running some evaluations on a good dataset. As shown in Figure 4, the accuracy of this approach is only 69%. However, Figure 4 shows that the accuracy of WSS-based algorithm is better than that of the Al-Sarhan algorithm. In addition, it was observed during the testing that Al-Sarhan’s approach failed to extract the correct root for simple words. For example, it extracted the root فعز (Faa′za) for the word isolate (فعزل Faa′zal), whereas the correct root is عزل (a′azal).

In light of the previous discussion, WSS-based algorithm is a competitive approach with new features that avoid possible flaws that may be produced by affix removal, which exist in traditional stemmers. However, WSS-based algorithm retrieves more than one candidate roots for about 9.9% of tested words, which reduces its efficiency against some traditional stemmers. Therefore, improving WSS-based by adding new rules that decrease the aforementioned percentage will greatly boost its efficiency.

5. Conclusions and future work

This paper has introduced a new approach, which is called WSS Algorithm, for extracting both three- and four-letter roots of Arabic words. The WSS algorithm does not remove affixes when extracting roots except some rendering in the preparation process to reduce the computations needed later. The algorithm was tested using the Holy Quran. The experiments showed that the accuracy of the WSS algorithm is 83.9%, and the percentage of words with more than one root candidate retrieved is 9.9% of the tested words. A comparison between the WSS stemmer and five popular Arabic stemmers showed that it achieves a competitive accuracy as it has occupied rank 3 among them. The WSS algorithm represents a promising approach for dealing with Arabic root extraction. Therefore, as future work, we plan to add more rules to reduce the percentage of words with more than one retrieved root candidate and enhance the accuracy of the algorithm.

Footnotes

Funding

This research received no specific grant from any funding agency in the public, commercial or not-for-profit sectors.

References

Duwairi

. Arabic text categorization. The International Arab Journal of Information Technology 2007; 4: 125–131.

Chowdhury

Aljlayl

Jensen

. Linear combinations based on document structure and varied stemming for Arabic retrieval. In: IIT at TREC 2002, Gaithersburg, MD, 2002.

Taghva

Elkhoury

Coombs

Arabic stemming without a root dictionary. In: The international conference on information technology: Coding and computing (ITCC’05), Washington, DC, 2005.

Momani

Faraj

. A novel algorithm to extract tri-literal Arabic roots. In: The IEEE/ACS international conference on computer systems and applications, proceedings, Los Alamitos, CA, 2007.

Al-Shammari

Lin

. Towards an error-free Arabic stemming. In: The 2nd ACM workshop on improving non-English web searching, New York, 2008.

Khoja

Garside

. Stemming Arabic text, http://zeus.cs.pacificu.edu/shereen/research.htm. (2008, accessed 1 September 2013).

Al-Sughaiyer

Al-Kharashi

. Arabic morphological analysis techniques: A comprehensive survey. Journal of the American Society for Information Science and Technology 2004; 55: 189–213.

Beesley

. Arabic morphological analysis on the Internet. In: The 6th international conference and exhibition on multilingual computing, Cambridge, UK, 1998.

Al-Fedaghi

Al-Anzi

. A new algorithm to generate Arabic root-pattern forms. In: The 11th national computer conference and exhibition, Dahran, Saudi Arabia, 1989.

10.

Mayfield

McNamee

Costello

. JHU/APL at TREC 2001: Experiments in filtering and in Arabic, video, and web retrieval. In: TREC 2001, Gaithersburg, MD, 2001.

11.

De Roeck

Al-Fares

. A morphologically sensitive clustering algorithm for identifying Arabic roots. In: The 38th annual meeting of the Association of Computational Linguistics, Hong Kong, 2000.

12.

Rogati

McCarley

Yang

. Unsupervised learning of Arabic stemming using a parallel corpus. In: The 41st annual meeting of the Association for Computational Linguistics, Jeju Island, Korea, 2003.

13.

Harmanani

Keirouz

Raheel

. A rule-based extensible stemmer for information retrieval with application to Arabic. The International Arab Journal of Information Technology 2006; 3: 265–272.

14.

Chen

Gey

. Building an Arabic stemmer for information retrieval. In: TREC 2002, Gaithersburg, MD, 2002.

15.

Kadri

Nie

. Effective stemming for Arabic information retrieval. In: The challenge of Arabic for NLP/MT conference, London, 2006.

16.

Boudlal

Belahbib

Lakhouaja

. A Markovian approach for Arabic root extraction. International Arab Journal of Information Technology 2011; 8: 91–98.

17.

Al-Nashashibi

Neagu

Yaghi

. An improved root extraction technique for Arabic words. In: The 2nd international conference on computer technology and development (ICCTD), Cairo, 2010.

18.

Al-Ameed

. A proposed new model using a light stemmer for increasing the success of search in Arabic terms. PhD Thesis, University of Bradford, Bradford, 2006.

19.

Hmeidi

Al-Shalabi

Al-Taani

. A novel approach to the extraction of roots from Arabic words using bigrams. Journal of the American Society for Information Science and Technology 2010; 61: 583–591.

20.

Al-Kabi

Al-Mustafa

. Arabic root based stemmer. In: The international Arab conference on information technology, Jordan, 2006.

21.

Al-Sarhan

Al-Shalabi

Kanaan

. New approach for extracting Arabic roots. In: The 2003 Arab conference on information technology, Egypt, 2003.

22.

Ghawanmeh

Al-Shalabi

Kanaan

. An algorithm for extracting the root for the Arabic language. In: The 5th international conference of the Business Information Management Association, Cairo, Egypt, 2005.

23.

Al-Kabi

Al-Radaideh

Akkawi

. Benchmarking and assessing the performance of Arabic stemmers. Journal Information Science 2011; 37: 111–119.