Stemming is a procedure used to reduce the inflected words by removing affixes from them. It is widely used in Natural Language Processing systems developed for various languages like English, Hindi etc. Punjabi is a low resource availability language spoken in northern regions of India and Pakistan. In Pakistan, Shahmukhi script is used to write Punjabi. While in India, Gurmukhi script is used. Various approaches are used for stemming natural language words such as Brute Force approach, Rule based approach, Statistical approach etc. In Gurmukhi scripted Punjabi language stemming, either the Brute Force approach or Rule based approach or a combination of both of these approaches have been used till now. This paper presents a comparative analysis of various stemmers developed so far for stemming Gurmukhi scripted Punjabi language words based on their methodology and accuracy. It will motivate further research in developing more efficient stemmers for Punjabi language. It will benefit the researchers to compare and understand the used approaches and the problems faced in adopting each approach.
A procedure adopted to reduce the inflected
words by removing any affixes attached to
them is called Stemming. Stemming is a very
common and crucial task performed in Natural
Language Processing (NLP) applications.
Many morphologically similar words can be
stemmed to the same stem word after
removing any suffixes or prefixes from them.
It improves the efficiency of further processes
adopted for information retrieval. It improves
the effectiveness of information retrieval by
helping to identify redundant information, to
remove irrelevant information from retrieval
and to optimize the retrieval by placing high
ranked information on the top [
Various approaches are used for stemming natural language words such as Brute Force approach, Rule based approach, Statistical approach etc. In brute force approach, a table of inflected words along with their stem words is maintained. To stem a word, that word is searched in the table for a match. If match occurs with some word, the related stem word is picked from the table. The approach is easy to implement and the accuracy is dependent on the table of words available in the database. In rule based approach, the affixes are removed by using some fixed rules. The input words are checked to have a group of characters at the end or beginning of each word. That set of characters (affix) is removed to get the stem word. In some words, an alternative set of characters is attached to the word to complete it.
In statistical approach, the distance
measure is calculated between the two words.
If the words are morphologically similar, they
will have low distance measure. For
morphologically unrelated words, distance
measure will be high. Using this measure, the
words of a document are grouped to make
clusters. In this way, morphologically similar
words will be grouped in each cluster. Then
the central word of each cluster is taken as a
stem word [
In Gurmukhi scripted Punjabi language stemming, either the Brute Force approach or Rule based approach or a combination of both of these approaches have been used till now. This paper analyses all those approaches and compares them with each other based on the methodology and accuracy. It will motivate further research in developing more efficient stemmers for Punjabi language. It will benefit the researchers to compare and understand the used approaches and the problems faced in adopting each approach. 1.1.
Punjabi language belongs to Indo-Aryan group of languages. Its word order in sentence is Subject-Object-Verb and is spoken by almost 100 million people residing in India, Pakistan and many other countries. It may be called Punjabi community. Table 1 shows the number of Punjabi speakers in some countries.
Punjabi is basically written in two different scripts; Perso-Arabic and Gurmukhi. PersoArabic is related to Persian script which is also called Shahmukhi, and Gurmukhi is derived from Landa, an old script of Indian subcontinent.
Jain et al. [
Agrawal et al. [
Bhadwal et al. [
Although there are positive effects of
stemming in various NLP applications, but
Wahbeh et al. [
Review of literature shows that stemming is used for a variety of NLP applications. It motivated the analysis of stemmers developed for Punjabi language. Only a handful of research papers found for this low resource availability Asian language.
In linguistics, an affix refers to either suffix or prefix. In Punjabi language, both types of affixes are used to make proper words for sentences. But in most cases, prefix changes the meaning of the word. So, in NLP applications, only suffixes are considered for removal. Table 2 shows some inflected words with their stem words. The table shows how the Punjabi words are dealt with linguistically to remove some characters and if required, substitute some alternative set of characters to complete the word.
Regardless of the language, stemming is an NLP process to find root words. So, this paper is understandable to the readers even without the knowledge of Punjabi and Gurmukhi script, because function of a stemmer is just to remove any affixes attached to a word. Therefore only brief introduction to Punjabi and Gurmukhi script is enough. This paper discusses the stemmers developed for Punjabi language Gurmukhi script. The paper discusses the methodologies used by researchers to stem the inflected words. In this paper, Gurmukhi scripted Punjabi language henceforth will be called Punjabi.
The significance of this analysis is that it discloses the gap in the NLP research for Punjabi language. It will motivate further research in developing more efficient stemmers for Punjabi using new ideas or by extending existing approaches. 4.1.
Kumar et al. [
The Input unit takes a Punjabi word and that word is sent to the Processing unit which searches for the word in a database of Punjabi inflected words and their stem words. If a word is found in the database, the corresponding stem word is considered as output stem word. If no match is found in database, then suffix removal technique is used to stem the word. The word ending is searched in a list of possible Punjabi suffixes. If the word ending matches with any one of the suffix present in the suffix list then the ending (suffix) is removed to get the stem word. The steps are shown in Algorithm 1 and graphically represented in Figure 1.
Algorithm 1: Earlier Stemmer for Punjabi 1: Input Punjabi Word for stemming. 2: Search the word in database. 3: If Found; goto (6). 4: Search the suffix of word in suffix list. 5: If Found; remove the suffix. 6: Display stem word. 7: End
Proposed stemmer was evaluated using three parameters i.e. Correctness, Effectiveness and Performance. Its accuracy is dependent on the number of words stored in the database. Researchers stored 28000 words in the database with 7100 root words for Brute Force search to find matching root word at the first step. So it reduced the chances of using the second step of removing suffix. More the number of words in the database more will be the correctness of the system. For the database they took words from a Punjabi-English dictionary and some online blogging and news websites.
Effectiveness of the system is determined by the behavior of the system in abnormal conditions, such as entering a word that does not exist. This stemmer simply displays the same word as the output. The problems of over-stemming and under-stemming can be further reduced by providing the large database of words. But if the word is not available in the database, these problems may arise in the second step i.e. removing suffix from the inflected word.
Performance of the system is determined by its output accuracy. This system is totally dependent on its database of 28000 words with 7100 root words. The accuracy was calculated by dividing the number of correct outputs by the total number of inputs. The calculated average accuracy of the system was 80.73%.
Kumar et al. [
Algorithm 2: Improved Version of Earlier Stemmer 1: Input Punjabi word for stemming. 2: Search the Word in Exception List. 3: If Found; goto (9). 4: Search the word in database. 5: If Found; goto (8). 6: Search the suffix of word in suffix list. 7: If Found; remove the suffix. 8: Display stem word. 9: End
Exception Found
List Matching
Matching
The proposed stemmer was evaluated for correctness, effectiveness and its performance. This stemmer used a database of 52000 words from various fields which contained 14400 root words. So it decreased the number of chances to execute the procedure of removing suffix from the inflected word. Increasing the number of words in the database will result in improved correctness of the output. Words were added to the database from various sources such as www.punjabionlinedictionary.com, Jag Bani Newspaper, Pardeep Punjabi to English Dictionary and some online blogging and news websites.
To measure the effectiveness of the stemmer, its behavior was verified in unusual conditions. For invalid input word, this stemmer provides the same word as output. A non-existing word in the database may result in over or under-stemming at suffix removal process. To overcome this problem, an exception list of approximately 200 words was created. These are those words that cause overstemming and under-stemming.
The output accuracy is assured if the output word is present as root word in the database. The accuracy was calculated by dividing the number of correct outputs by the total number of inputs. The calculated average output accuracy of the stemmer was 81.27%.
Gupta and Lehal [
The original stemming algorithm composed of 19 steps and in first 18 steps suffix removal and/or suffix substitution was done based on the suffix attached to the word. Some suffixes were just removed from the end of the word but in some cases, suffix was removed and then another suffix was substituted. In 19th step of the algorithm, the stemmed word was searched in the list. If matched, it was taken as a Punjabi noun or proper name. The Algorithm 3 shows the reconstructed steps taken by the stemming process. Figure 3 shows these steps graphically.
Algorithm 3: Reconstructed Algorithm of Stemmer for Only Nouns & Proper Names 1: Input Punjabi word for Stemming. 2: Match end of the word with expected suffix. 3: If Not Matched; More expected suffix exist; goto (2) with next expected suffix. 4: Remove matched suffix from word. 5: If required, substitute a suffix. 6: Find word in noun morph/names list. 7: If Not Found; goto (9). 8: Display stem word. 9: End.
The stemmer was analyzed with 50 Punjabi documents obtained from various Punjabi news articles and other resources. It was tested to have 87.37% accuracy rate. The accuracy was calculated by dividing the number of correct outputs by the total number of inputs. The error percentage of the stemmer was also analyzed. The error percentage was also calculated separately for three different reasons.
Word
Gupta [
For each category of suffixes separate rule
based algorithm was written. But for stemming
of proper names and nouns, the researcher
reused the stemming algorithm from his
already published paper [
Algorithm 4: Automatic Stemmer for All Category of Words 1: Input Punjabi Word for stemming. 2: Find Word in noun morph OR Names dictionary OR Dictionary. 3: If Found; goto (17). 4: Call (Proper Names and Nouns Sub
Stemmer). 5: Find Stemmed Word in noun morph OR
Names dictionary. 6: If Found; goto (17). 7: Call (Verb Sub-Stemmer). 8: Find Stemmed Word in dictionary. 9: If Found; goto (17). 10: Call (Adjective/Adverb Sub-Stemmer) 11: Find Stemmed Word in dictionary. 12: If Found; goto (17). 13: Call (Pronoun Sub-Stemmer) 14: Find Stemmed Word in dictionary. 15: If Found; goto (17). 16: Show Error. 17: Display Word. 18: End.
Match in Noun
Morph/ Names Dictionary
Match in Dictionary
Dictionary h c t a M h c t a M h c t a M h c t a M
Stem Word The overall accuracy percentage of the stemmer was 87.2% and error percentage was 12.8%. The accuracy was calculated by dividing the number of correct outputs by the total number of inputs.
Puri et al. [
A Named Entity database was prepared with 26992 distinct names used in Punjabi language. Most of the words were taken from news articles and university rolls. This list was prepared to ensure that these words should be skipped while stemming, because stemming of these Named Entities will change them altogether. A suffix list consisting of 75 Punjabi language suffixes was created manually by analyzing news articles. These are the suffixes to be removed and the suffixes to be substituted (if required) for stemming. The substitution suffix was NULL if there was no need of any suffix substitution.
Some of the suffix stripping rules provided false positive in stemming for a few words, yet those rules were important to stem a good quantity of words. Those rules were analyzed and an Exception list of those words was generated.
The algorithm proceeds by checking the word length. If its length is less than the minimum length (constant) then it need not be stemmed. If it is not, the word is searched in Named Entity database. If a match occurs, the word need not be stemmed. If the word is not found in Named Entity database, then it is searched in Exceptions list. If a match occurs, the word is ignored and not stemmed. If the word is not found in Exceptions list then its suffix is removed by searching the suffix in the suffix list. The substitution suffix (if available . n i M = >
t s i x toE Find in N Excepti on List t s i x E t o N
with Substitution
Suffix
Stemmed Word t isx Find in E Suffix List
Dictionary in suffix list) is also added to the end of the word. Finally the stemmed word is searched in dictionary. The word is taken as stem word if it is available. Algorithm 5 shows the stemming process and Figure 5 graphically represents the process.
Algorithm 5: Stemmer using WordNet Database 1: Input Punjabi Word for stemming. 2: If Length (Word) < Min-Length; goto(9) 3: If Word Found in Named Entity List; goto(9) 4: If Word Found in Exception List; goto(9) 5: If Word Suffix Not Exist in Suffix List; goto(9) 6: Replace Suffix with Substitution Suffix 7: If Stemmed Word Not exist in dictionary; goto(9) 8: Output Stem Word 9: End.
The stemmer was tested with a sample of 1000 news articles. It was tested by computing the F-Measure value using the counting of words as follows:
C = correctly stemmed
U = under-stemmed O = over-stemmed (1) (2) Recall = C / ( C + U ) Precision = C / ( C + O )
The calculated Recall = 94.83%
Precision = 90.84% From (1) and (2):
F-Measure = 92.79%.
From the analysis of these stemmers, it is
clear that each stemmer developed for Punjabi
language provides accuracy improvements in
its own way. The stemmer by Puri et al. [
We can calculate the accuracy of stemmer
developed by Puri et al. [
C = correctly stemmed
U = under-stemmed
O = over-stemmed
So, Input Word Count = C + U + O
Using Calculations by Puri et al. [
Recall = C / ( C + U ) × 100 = 94.83
From the graph it is clear that the overall
accuracy of stemmers is reduced continuously
after the stemmer [
Stemming is a building block of NLP. Research to stem Punjabi words is limited to a handful of research papers. The initiatives by researchers, no doubt, are praiseworthy, but this research field requires more efforts as compared to the research for other languages such as English, Hindi etc. Each stemmer developed for Punjabi language provides accuracy improvements in its own way. The table lookup approach is used in almost all Punjabi language stemmers to check either the word is already a stem word or the word is correctly stemmed after stemming process. For these stemmers, table lookup is the only way to check for the correctness of the stemming process. The rule based approach is also used along with table lookup to obtain a stem word by suffix stripping from the inflected words. Suffix substitution is used to complete the word, if required. This paper explored these approaches in an analytical manner with their accuracy comparisons. The significance of this analysis is that it disclosed the gap in NLP research for Punjabi language. There is a scope of research to invent more efficient stemmers for Punjabi language using new ideas or by extending the existing approaches.