1 Introduction
One of the challenges in textual information extraction is word variants normalization. This task becomes harder for inflectional languages such as Arabic.
In the concatenative languages (Sproat Reference Sproat1992; Menn Reference Menn1995) like English, words are generally in the form prefix.stem.suffix and the problem is then to find frontiers (i.e., the starting letter of stem and suffix). In more complex morphologies, for instance Arabic (Soudi and van den Bosch Reference Soudi and van den Bosch2007; Jurafsky and Martin Reference Jurafsky and Martin2009), the stem could not be considered as the normal carrier of the word's and variants' broad meaning. This is due to the internal changes that affect the word with no substantial effect on the meaning. For instance, stemming the plural form
([kutub]: books)(IPA 1999) will not allow the match of either the singular form
([kɪtɑːb]: book) or the smallness form
([kutajɪb]: small book). Both have an extra internal letter: respectively
([ɑː]: 1st Arabic letter) and
([j]: 28th Arabic letter) at the third position of each.
Arabic is recognized to be highly inflectional and classical stemming techniques are not so effective and perform much worse than they do in concatenative languages.
Being language independent, unsupervised approaches seem to be the oldest candidates to handle non-European languages such as Arabic.
The oldest published work on unsupervised word segmentation is due to Zelig Harris who suggested in the 1950 s a process to break a phonetic text into morphemes (Harris Reference Harris1955) using only successors numbering. The principle is to count at each position of the word the number of successors and/or predecessors observed in a corpus; positions where the number of predecessors/successors exceeds a threshold k are marked as frontiers.
Example 1.1
Figure 1 shows the curve of successors counts for the word ‘writing.’ The curve rises for the substring ‘writ’ which is actually a stem.
Successors counts variation for the word ‘writing’.
Figure 2 shows the curve of successors counts of the Arabic word 
([welkɪtɑːb]: and the book) observed in a spelling dictionary. Successors number of the prefix 
([wel]: and the) is a clear peak.
Successors counts variation for the word 
.
Hafer and Weiss (Hafer and Weiss Reference Hafer and Weiss1974) adapted Harris's technique to word segmentation and tested the use of fifteen different setups of four measures:
(1) Successors and predecessors threshold: Same as Harris's original approach.
(2) Peaks versus plateaus: Every peak or plateau is considered as a segmentation position.
(3) Complete word: A prefix is considered as a segment if and only if it matches a word in the corpus.
(4) Entropy: Let w = a 0. . . a n−1 be a word of n letters (ai). Let wi be the prefix a 0. . . a i−1 and cnt(wi) the number of words in the corpus sharing the prefix wi. The entropy at a position i is as follows
where l is a letter over an alphabet
\[
H_{w_i} = \sum_{l\in\A}-\frac{cnt(w_i.l)}{cnt(w_i)}\times\log\frac{cnt(w_i.l)}{cnt(w_i)}
\] and the string concatenation. The position at which the entropy exceeds a threshold is considered as cutoff point.
Xu and Croft (Reference Xu and Croft1998) proposed a co-occurrence-based measure to build a stemmer or refine an existing one. Their basic hypothesis is the word forms that should be conflated for a given corpus will co-occur in documents from that corpus. The same approach has been tested on Arabic (Larkey, Ballesteros and Connell Reference Larkey, Ballesteros and Connell2002) and results show that the co-occurrence approach alone is not so effective for Arabic as it is for English and Spanish.
Rogati, McCarley and Yang (Reference Rogati, McCarley and Yang2003) have used a statistical translation with an English stemmer and a parallel corpus to build an unsupervised Arabic stemmer, although the building itself is supervised. The principle is to build a translation model using a parallel corpus. The translation model allows them to map the English stems carried out by an English stemmer to their Arabic translations. This initial Arabic stemmer is deployed to segment words of the Arabic side of the parallel corpus. These two steps are iterated to improve both the accuracy of the translation model and the Arabic stemmer.
Lee et al. (Reference Lee, Papineni, Roukos, Emam and Hassan2003) used a manually segmented corpus (suffixes, prefixes dictionary) to build a stemmer. Their stemmer attempts to carry out all possible segmentations following the template prefix*.stem.suffix* then checks them against the manually built corpus.
Creutz and Lagus (Reference Creutz and Lagus2002) proposed two morpheme-like segmentation methods. The first based on Minimum Description Length (MDL) (Grnwald Reference Grnwald2007), and the second based on Maximum Likelihood (ML).
Sharma, Kalita and Das (Reference Sharma, Kalita and Das2002) used a set of heuristics to build a dictionary of segmented words for Assamese language. Monson et al. (Reference Monson, Lavie, Carbonell and Levin2004) propose an automatic extraction of inflectional classes from a corpus. Claimed to be unsupervised and language independent, the technique was tested for Spanish.
Karagol-Ayan, Doermann and Weinberg (Reference Karagol-Ayan, Doermann and Weinberg2006) use longest common substring and edit distance to segment into stem-affix words in a limited and eventually noisy dictionary.
Other unsupervised morphology related approaches have been investigated in the other languages (Goldsmith Reference Goldsmith2001; Snover, Jarosz and Brent Reference Snover, Jarosz and Brent2002).
A more simplistic approach, often said light stemming, is to strip out unconditionally all common prefixes and suffixes (Chen and Gey Reference Chen and Gey2002; Larkey Ballesteros and Connell Reference Larkey, Ballesteros, Connell, Ide, Vronis, Baayen, Church, Klavans, Barnard, Tufis, Llisterri, Johansson, Mariani, Soudi, van den Bosch and Neumann2007). This seems to perform acceptable results in information retrieval. This may be due to the fact observed and used in (Xu and Croft Reference Xu and Croft1998).
Baroni, Matiasek and Trost (Reference Baroni, Matiasek and Trost2002) proposed to extract a list of related words from a plain text using two metrics: the edit distance and mutual information, where Schone and Jurafsky (Reference Schone, Jurafsky, Cardie, Daelemans, Nédellec and Sang2000) use a combination of distribution and semantic information.
In Section 3, we describe our approach intended to define a metric that assesses how morphologically close are two words to each other. This metric could be simplified to the binary decision: whether two words are morphologically related or not. Section 4 discusses the tests and results.
2 Morphological relatedness
In word variants matching, stemming and radicals extraction are the process of going up to the morphological origins of the two compared variants to check whether these origins match or not.
This approach faces two main challenges:
(1) Which origin is appropriate?
(2) How accurate is the origin retracing?
The first challenge is the known debate on which is the best normal form: stem or root.Footnote 1 The second challenge has been paid much more attention by the research community. This resulted in many stemming approaches, where less mature approaches are developed for radicals extraction (de Roeck and Al-Fares Reference de Roeck and Al-Fares2000; Daya, Roth and Wintner Reference Daya, Roth and Wintner2008; Boudlal et al. Reference Boudlal, Belahbib, Lakhouaja, Mazroui, Meziane and Bebah2011).
We claim that another option is to compare directly the two words in order to say how morphologically close they are to each other. In other terms, how likely are they derived from the same morphological origin? With no need to compute that origin, in this section we discuss our approach to measure this closeness.
Let w 1 and w 2 be the two words whose morphological relatedness we would like to know. Let freq(a) be the frequency (count) of the letter a ∈ 
observed in some corpus. LCS(w 1, w 2) is the longest sequence common to w 1 and w 2 (Hsu and Du Reference Hsu and Du1984; Crochemore, Hancart and Lecroq 2007) and LCS(w 1, w 2) all letters of w 1 and w 2 not involved in LCS(w 1, w 2). ‖w‖ is the size of the word w ∈ *. Finally w[i] is the i th letter of the word w.
The morphological relatedness MR is computed as follows:
\begin{eqnarray*}
MR&=&\sum\limits_{i=1}^{\len{LCS(w_1,w_2)}} \log{\left(\frac{1}{freq(LCS(w_1,w_2)[i])}\right)}\\ &&-\,\sum\limits_{i=1}^{\len{\overline{LCS(w_1,w_2)}}} \log{\left(\frac{1}{freq(\overline{LCS(w_1,w_2)}[i])}\right)}
\end{eqnarray*}Example 2.1
Let w 1 = 
([kɪtɑːb]: a book) and w 2 = 
([kutub]: books).
We have
\[
LCS(w_1,w_2)=\text{'\RL{كـ ـتـ ب}'}
\]
Then
\begin{eqnarray*}
MR(w_1,w_2)&=&\log\left(\frac{1}{freq(\text{'\RL{كـ}'})}\right)\\
&&+\,\log\left(\frac{1}{freq(\text{'\RL{ـتـ}'})}\right)\\
&&+\,\log\left(\frac{1}{freq(\text{'\RL{ب}'})}\right) \\
&&-\, \log\left(\frac{1}{freq(\text{'\RL{ا}'})}\right)
\end{eqnarray*}2.1 The intuition beneath
An Arabic word is a sequence of (with respect to our purpose) letters of two types: (1) affixes, and (2) core letters. Affixes are common to all words built following the same pattern as the suffix “ing” is common to English words “*ing”. For instance, the letter
is a common infix to Arabic words built following the pattern
such as:
The idea is that letters in affixes are expected to be of high frequencies since they often participate in words even when they are not of their core structure. However, the core letters are supposed to be of much lower frequencies. Using the formula above:
• Lower are the frequencies of the LCS letters, higher is the MR.
• Longer is LCS, higher is the MR.
• Longer is LCS, lower is the MR.
• Lower are the frequencies of LCS letters, lower is the MR.
This reflects the intuition:
• When a LCS letter has a low frequency, this means that most likely the two words share a core letter.
• When a LCS letter has a high frequency, this means that most likely the shared letter is an affix one.
Analogically:
• When a LCS letter has a low frequency, this means that most likely a core letter of one word is missing in the second.
• When a LCS letter has a high frequency, this means that most likely only an affix letter in the one word is missing in the second.
Hence:
• More core letters are common, more likely the two words are derived from the same morphological origin.
• More core letters are uncommon, more likely the two words are not derived from the same origin.
2.2 MR interpretation
One of the objectives is to use the MR to find the word classes, where words are of the same class if and only if they are derived from the same morphological origin. Let w 0 be an Arabic word and S = w 1, w 2, . . . , wn a set of Arabic words. We would like to extract five words in S that are variants (i.e., derived from the morphological origin) of w 0 using only the MR measure. We have to:
(1) compute all MRs: MR(w 0, w 1), MR(w 0, w 2), . . . , MR(w 0, wn),
(2) sort the MRs in a descending order, and
(3) keep the five words with the five highest MRs.
Of course, there may be less (eventually none) than five actual variants in S and the steps above will lead to a wrong result. However:
• In a real application such as information retrieval systems, the number of sought variants could be adjusted to fit the required results.
• A threshold for the significant MR can be defined.
2.3 Complexity
LCS(w 1, w 2) can be computed in O(‖w 1‖ × ‖w 2‖) time and O(min(‖w 1‖, ‖w 2‖)) space (Crochemore et al. Reference Crochemore, Hancart and Lecroq2007). freq is computed over a corpus only once and requires a table of O(#) space where # is the size of the alphabet. The access to a freq's entry requires a constant time. Therefore, the time and space complexities of the morphological relatedness computation depend only on the time and space complexities of the computation of LCS(w 1, w 2), which are respectively O(‖w 1‖ × ‖w 2‖) time and O(min(‖w 1‖, ‖w 2‖)) space.
3 Tests and results
Our investigation targeted traditional formal Arabic for the following reasons:
(1) Traditional Arabic has many differences in terms of vocabulary as well as grammar with the modern Arabic in use.
(2) Many collections are in pure traditional Arabic.
(3) To the best of our knowledge, no published work targets explicitly the old traditional Arabic.
(4) Basically, generalizing our approach to a lesser restrictive vocabulary such as modern Arabic should be straight.
Performance of an information retrieval (IR) system involves factors other than the normalization approach. It should be then arguable to evaluate the measure independently of any information retrieval system.
We consider the binary relevance in which two words w 1 and w 2 are relevant to each other if they share at least one root. For instance, the word 
has at least two meanings since it has at least two roots:
The word
([ʔɪːnɑːʕun]: Ripening) has the root
and
are then relevant to each other since they share the root
.
3.1 The test dataset
We have extracted the letters' frequencies (freq) from a corpus exceeding 500k distinct words dumped from an old Arabic dictionary (
1965). We then mapped more than 200k words to their roots using ElixirFM (Smrž Reference Smrž2007) morphological analyzer, which is based on Tim Buckwalter's morphological analyzer (Buckwalter Reference Buckwalter2004).
For every word in a sample of 80,629 words randomly chosen among the 200 k words, we have:
(1) Extracted the set of all related words Rroot(w) in the 200k corpus where:
Where:
\[R_{root}(w)=\{w_i\in\text{Corpus}: rel(w_i,w)=1\}\]
where roots(w) is the set of w's roots.
\[rel(w_i,w)=\begin{cases}
1&\text{if }roots(w)\cap roots(w_i)\neq\emptyset\\
0&\text{otherwise}
\end{cases}
\](2) Extracted the set {w 1, . . ., wk} of k words having respectively the k highest MR scores with k = #roots(w) (cardinality of roots(w)).
(3) Measured the Normalized Discounted Cumulative Gain (NDCG) (Sakai Reference Sakai2007) and the R-precision (Buckley and Voorhees Reference Buckley and Voorhees2000; Aslam and Yilmaz Reference Aslam, Yilmaz, Herzog, Schek, Fuhr, Chowdhury and Teiken2005).
In our case:
Where
\[NDCG(w)=\frac{DCG(w)}{IDCG(w)}\]
\[DCG(w)=rel(w_1,w)+\sum_{i=2}^{k}\frac{rel(w_i,w)}{\log_2(i)}\]
\[IDCG(w)=1+\sum_{i=2}^{k}\frac{1}{\log_2(i)}\]\\
Intuitively, the NDCG reflects how relevant and ordered are the results. The prefect NDCG is 1, which occurs when all the results are correctly ordered and all of them relevant. In our case, this occurs when all results share at least one root with w since we adopted the binary relevance. When a non-relevant result is carried out, the NDCG decreases depending on the ranking of that non-relevant result. If the non-relevant result is carried out first, the NDCG will be lower than when the non-relevant result is carried out at the second or nth position. Higher is n, higher is the NDCG. However, R-precision shows among the results how many are actually relevant, and is calculated as follows:
\[R-\text{precision} = \frac{\sum\limits_{i=1}^{k}rel(w_i,w)}{k}\]
3.2 Collation
In order to avoid mismatches induced by variations in letter forms, we introduce the following normalization.
(1)
has been replaced by (2)
and by (3) finally,
by
A subset of the collation rules given above has been tested (Khorsi Reference Khorsi2012) and the results show its positive impact.
3.3 Results and discussion
The global averages of NDCG and R-precision reached respectively 34.89% and 26.88%. Figures 3 and 4 show the NDCG and R-precision distribution over the test sample.
NDCGs distribution.
R-precisions distribution.
Every bar gathers the words with regard to their rounded NDCGs and R-precisions. For instance, 9,235 words have their NDCGs around 20% and 13,552 have their R-precision around 20%. Most of the results do not reach 50% of either the NDCG or the R-precision. Yet a significant portion exceeds the 50% in both measures.
In the paragraphs below, we examine the NDCG and R-precision values variations against various factors to see whether a clear influence of any could be distinguished and thereby to see what makes the NDCG and R-precision increase and what makes them decrease. One suspected factor is the relative length of affixes. Intuitively, when the prefix and/or the suffix is too long, this will have two main effects:
(1) A variant which has not that long affix will have its MR low since all letters of the affixes will be discounted.
(2) A non-variant word which has that long affix will have its MR high since all common letters are counted in the MR and core letters which are not common will not make the MR decrease enough.
Let a word w = u·w 0·v and its variant w′ = u′·w 0·v′. Let another word x = u·x 0·v where 
is the string concatenation. w and w′ share w 0 where they differ in u.v.u′·v′. However, w and x share u·v and differ in w 0·x 0.
Figures 5 and 6 show the variations against the numbers of related words #Rroot(w).
NDCGs variation over #Rroot(w).
R-precisions variation over #Rroot(w).
Both give the impression that words with high form variability tend to have relatively smaller portion of variants covered by the MR measure, which is terminologically said low recall. This is due to the fact that a high number of variants means occurrence of a high number of inflectional and mutating letters such as long vowels. Even with high frequencies, their abundance reduces the MR and makes words not actually relevant but with lesser inflectional letters jump up in the ranking. On the counter part, the only words reaching a perfect ranking 100% are those with low variability.
For sizes of words (see Figures 7 and 8).
NDCGs variation over ‖w‖.
R-precisions variation over ‖w‖.
Unlike Harris-based approaches, which are affected by the length of words and affixes, our's does not seem to show any influence of the word length. Notice that the longest word in our corpus is that of eleven letters, the smallest is that of two, and the length average is 5.38.
Figures 9 and 10 show the impact of the mean and variance of the frequencies of letters in root(w).
Impact of the mean and variance of frequencies of root(w)'s letters on NDCG.
Impact of the mean and variance of frequencies of root(w)'s letters on R-precision.
As expected, in both, the main part of results shows that the more letters of the roots are of lower frequencies, the higher are the NDCG and R-precision. Indeed, the lower are the frequencies of the root letters, the better is the word, and its variants distinguishable.
3.4 Results for a fixed number of top variants
The analysis above was on the overall results. In the paragraphs below, we examine the performance of our approach in extracting a fixed number of variants.
For five top variants, the NDCG and R-precision reached respectively 82.76% and 78.68% (see Figure 11).
NDCG and r-precision for the top five variants.
This clearly shows a good effectiveness in the extraction of a fair number of variants. Analogically, Figures 12 and 13 show respectively the NDCG and R-precision for different numbers of variants.
NDCG for the n top variants.
R-precision for the n top variants.
For a wider view, Figure 14 shows how NDCG and R-precision are varying over the number of the extracted variants.
NDCG and r-precision averages for different sizes of top variants.
4 Conclusion
We discussed results of the use of an unsupervised evaluation of words' morphological relatedness. This measure is intended to assess how likely two words are derived from the same morphological origin, which in our study are the radicals. This measure may be viewed as an alternative to radicals extraction and stemming. The main features of our approach are:
• Its computation is entirely unsupervised and no linguistic knowledge is required.
• Its computation is fast and fit requirements of real applications such as information retrieval systems.
• Its time and space complexity depend only on the sizes of the two compared words.
• The comparison does not need the computation of the normal form (i.e., origin, e.g., stem, root). In the traditional approaches, both the normal forms finding and comparison are empirical, which increases the risk of error.
Results show that when the letters of the root have high frequencies, the measure is not able to effectively discriminate the variants. This appeals to think about adding a weighting factor to the measure. One option could be a weight that is refined iteratively. This may make the computation greedier in time. Another improvement is to extend the frequencies to n-grams. When the core letters have high frequencies, their combination with the other core letters will decrease the problematic high frequency and perform better discrimination. On the counter part, it will complicate the choice of the common part used to compute the relatedness. Recall that we have used here the LCS as a common part. Moreover, the use of the n-grams will also decrease the frequencies of the non-core letters making them a confusing factor. Take the example of two unrelated words but sharing the same long prefix such as 
([wel]: and the). The frequency of the whole prefix is much lower than its separated letters. Another potential improvement is to introduce an unsupervised stemming before the computation of the MR. This will avoid the problem of long affixes highlighted above. Still, our measure shows a good effectiveness on the extraction of a fair number of variants.
