Elamur Research⌕
☰
home / papers / 2017 / Parallel Hardware for Faster Morphological Analysis

Parallel Hardware for Faster Morphological Analysis

Paper · 2017 · Issam Damaj, Mahmoud Imdoukh, Rached Zantout American University of Kuwait et al.

Summary

The paper tackles the cost of Arabic morphological analysis. Arabic verbs carry prefixes, suffixes and infixes, and the infix letters can coincide with root letters, so extracting a root takes many rule checks. The authors build a linguistic-based (LB) stemmer that extracts verb roots and adds extra infix handling. They model it as concurrent processes (Generate Stems, Filter by Size, Compare Stems and Extract Root, Substring Truncation) and implement it three ways: as software on a multi-core CPU, as a non-pipelined FPGA processor, and as a pipelined FPGA processor. The pipelined core reaches about 2.08 million words per second, roughly 5,571 times faster than the software version. Root-extraction accuracy is 87% on the Holy Quran and 90.7% on its Chapter 29, Surat Al-Ankabut, with results checked against the Khoja stemmer. The authors argue that NLP research should treat parallelism and hardware/software co-design as first-class concerns. They also propose hardware metrics as a way to profile NLP algorithms.

Key points

  • Speed: the parallel processor reaches 2.08 MWps, a 5571.4× speedup over software. Pipelining adds a further 5.18× over the non-pipelined core.
  • Clock and area: the cores run at only about 10.4 MHz (non-pipelined) and 10.78 MHz (pipelined). The pipelined core still achieves 151.85 Wps/ALUT and 10,197 Wps/LR.
  • Complexity: the sequential algorithm is O(n²), and several parallel sub-processes become constant-time. Stem comparison stays the bottleneck, and the authors suggest a tree search could make it O(log n).
  • Scale of the problem: the Qutrub tool generates 82 surface forms for the single root "study", which collapse to 36 once diacritics are removed.
  • Ablation on frequent Quran roots: infix processing matters a lot. For the hollow root كون (1390 true occurrences), Khoja finds only 32, the proposed stemmer with infix processing finds 765, and without it 161. On several other roots, however, Khoja finds more.

Interesting ideas

  • I1. Generate every candidate stem from a word at once, prune by length, then validate against a closed list of known roots, turning analysis into a parallel filter-and-match pipeline.
  • I2. Evaluate the same algorithm with and without one rule component (infix processing) on a per-frequent-item basis, exposing where the component carries the result.
  • I3. Compare against a strong baseline item by item rather than with one aggregate score, which revealed a specific blind spot (Khoja on a hollow verb root).
  • I4. Profile NLP code with throughput, throughput-per-resource and degree of parallelism, not just accuracy, so that design trade-offs become visible.
  • I5. Identify the one inherently sequential step (stem comparison) as the critical path and propose a tree search to shrink it.

For Mova

How these ideas could serve Mova, our small open language model — its files, stages and tests:

  • I1 (tokens): the lemmatizer for irregular English forms could produce all candidate lemmas in parallel and keep only those found in the lexicon, with each rejection logged for explainability.
  • I2 (learn): per-lemma or per-relation ablation tables could serve as negative controls showing which repair rules or modules actually earn their keep.
  • I3 (learn): reporting gparse-versus-perceptron disagreements per construction would localize systematic failures that a single LAS number hides.
  • I4 (tree): tracking sentences per second per GPU memory unit for gparse alongside LAS would make parser design decisions measurable.
  • I5 (world): lookups into the compiled knowledge (verb classes, WordNet ontology) could use indexed or trie structures so they do not become the bottleneck of the pipeline.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

 Institutions

Also on the byline: American University of Kuwait · Rafik Hariri University.

📚 Shelves 5 Computer Science · 9,086 works Artificial Intelligence · 8,889 works Arts and Humanities · 9,296 works Language and Linguistics · 9,206 works Hardware and Architecture · 38 works

🧭 Topics 3 Semitic languages · 1,484 works Morphology · 277 works GPU & parallel computing · 7 works

Cite

Cite as Issam Damaj, Mahmoud Imdoukh, Rached Zantout American University of Kuwait and Rafik Hariri University). 2017. Parallel Hardware for Faster Morphological Analysis. arXiv:1904.07148 · Computer and Information Sciences, Elsevier. 30(2018) 531-546.

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.1016/j.jksuci.2017.07.003 · arXiv 1904.07148

@misc{damaj2017parallel,
  title = {{Parallel Hardware for Faster Morphological Analysis}},
  author = {Issam Damaj, Mahmoud Imdoukh, Rached Zantout American University of Kuwait and Rafik Hariri University)},
  year = {2017},
  doi = {10.1016/j.jksuci.2017.07.003},
  eprint = {1904.07148},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.1016/j.jksuci.2017.07.003}
}

References

49 references, 0 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. Abu Shquier, M.M., Alhawiti, K.M., 2015. Novel prefix tri-literal word analyser: rule-based approach. J. Comput. Sci. 11 (4), 627–638. http://dx.doi.org/10.3844/jcssp.2015.627.638. ↗
  2. Abu-Errub, Aymen, Odeh, Ashraf, Shambour, Qusai, Al-Haj Hassan, Osama, 2014. Arabic roots extraction using morphological analysis. Int. J. Comput. Sci. Issues (IJCSI) 11 (2), 128. find
  3. Agarwal, Basant, Mittal, Namita, 2016. Machine learning approach for sentiment analysis. Prominent Feature Extraction for Sentiment Analysis. Springer International Publishing, pp. 21–45. ↗
  4. Al-Bawab, M., Al-Tayyan, M., 1998. Computerized processing of Arabic morphology. Arabian Mag. Sci. 32, 6–13. find
  5. Al-Khalifah, Z.M., 1996. Automated Morphological Analysis of Words (MSc Thesis). Department of Computer Science, College of Computer and Information Systems, King Saud University, Riyad, Kingdom of Saudi Arabia. find
  6. Al-Shalabi, Riyad, Evens, Martha, 1998. A computational morphology system for Arabic. Proceedings of the Workshop on Computational Approaches to Semitic Languages. Association for Computational Linguistics, pp. 66–72. find
  7. Al-Sughaiyer, Imad A., Al-Kharashi, Ibrahim A., 2004. Arabic morphological analysis techniques: a comprehensive survey. J. Am. Soc. Inf. Sci. Technol. 55 (3), 189– 213. ↗
  8. Asaad, Amal, Abbod, Maysam, 2014. Arabic text root extraction via morphological analysis and linguistic constraint. 16th International Conference on Computer Modelling and Simulation. IEEE, pp. 125–130. find
  9. Boubas, Anas, Lulu, Leena, Belkhouche, Boumediene, Harous, Saad, 2011. GENESTEM: A novel approach for an Arabic stemmer using genetic algorithms. Proceedings of the 2011 International Conference on Innovations in Information Technology (IIT), pp. 77–82. find
  10. Boudlal, Abderrahim, Bebah, Mohamed, Lakhouaja, Abdelhak, Mazroui, Azzeddine, Meziane, Abdelouafi, 2011. A Markovian approach for Arabic root extraction. Int. Arab J. Inf. Technol 8 (1), 91–98. find
  11. Buckwalter, Tim. 2002. Buckwalter Arabic Morphological Analyzer Version 1.0. ↗
  12. Cohen, Jonathan D., 1998. Hardware-assisted algorithm for full-text large-dictionary string matching using n-gram hashing. Inf. Process. Manage. 34 (4), 443–464. ↗
  13. Dahdah, A., 1995. ‘ ﺔ ﻴ ﺑ ﺮ ﻌ ﻟ ﺍ ﻝ ﺎ ﻌ ﻓ ﻷ ﺍ ﻒ ﻳ ﺮ ﺼ ﺗ ﻢ ﺠ ﻌ ﻣ ’ (Dictionary of the Conjugation of Arabic Verbs). Librairie du Liban, Beirut, Lebanon. find
  14. Damaj, Issam W., 2006. Parallel algorithms development for programmable logic devices. Adv. Eng. Softw. 37 (9), 561–582. ↗
  15. Damaj, Issam W., 2007. Parallel algorithms development for programmable devices with application from cryptography. Int. J. Parallel Programm. 35 (6), 529–572. ↗
  16. Damaj, Issam., Diab, Hassan., 2003. Performance analysis of linear algebraic functions using reconfigurable computing. J. Supercomput. 24 (1), 91–107. ↗
  17. Damaj, Issam, Kasbah, Safaa, 2017. An analysis framework for hardware and software implementations with applications from cryptography. Comput. Electr. Eng. http://dx.doi.org/10.1016/j.compeleceng.2017.06.008. ↗
  18. El-Affindi, M., 1991. An algebraic algorithm for Arabic morphological analysis. Arabian J. Sci. Eng. 16 (4), 605–611. find
  19. El-Affindi, M., 1998. Performing Arabic morphological search on the internet: a sliding window approximate matching (SWAM) algorithm and its performance. Dept. of Computer Science. CCIS, KSU. Saudi Arabia. find
  20. Gadri, Said, Moussaoui, Abdelouahab, 2015. Information retrieval: A new multilingual stemmer based on a statistical approach. 2015 3rd International Conference on Control, Engineering & Information Technology (CEIT). IEEE, pp. 1–6. find
  21. Grossi, Roberto., 1992. A fast VLSI solution for approximate string matching. Integration VLSI J. 13 (2), 195–206. ↗
  22. Hamalawy, A., 2009. ‘ ﻑ ﺮ ﺼ ﻟ ﺍ ﻦ ﻓ ﻲ ﻓ ﻑ ﺮ ﻌ ﻟ ﺍ ﺍ ﺬ ﺷ ’ (The Art of Morphology). IslamKotob, Beirut, Lebanon. find
  23. Hamandi, Lama, Zantout, Rached, Guessoum, Ahmed, 2002. Design and implementation of an Arabic morphological analysis system. Proceedings of the International Conference on Research Trends in Science and Technology 2002, 325–331. find
  24. Hamandi, Lama, Damaj, Issam, Zantout, Rached, Guessoum, Ahmed, 2006. Parallelizing arabic morphological analysis: towards faster arabic natural language processing systems. Proc. CIBITIC, 455–459. find
  25. Hegazi, N., Elsharkawi, A., 1986. Natural Arabic language processing. In Proceedings of the 9th National Computer Conference, vol. 2. find
  26. Hlal, Y., 1987. Information systems and Arabic: the use of Arabic in information systems. Linguistics Signal Inf. Process., 191–197 find
  27. Kasbah, Safaa J., Damaj, Issam W., Haraty, Ramzi A., 2008. Multigrid solvers in reconfigurable hardware. J. Comput. Appl. Math. 213 (1), 79–94. ↗
  28. Khodor, Mohammad Z., Zaki, Akram M., 2011. A Statistical Study of the Words of the Holy Quran. In: Arabic ‘‘ ﻢ ﻳ ﺮ ﻜ ﻟ ﺍ ﻥ ﺁ ﺮ ﻘ ﻟ ﺍ ﺕ ﺎ ﻤ ﻠ ﻜ ﻟ ﺔ ﻴ ﺋ ﺎ ﺼ ﺣ ﺍ ﺔ ﺳ ﺍ ﺭ ﺩ ,” in the Third Arabic Language and Literature Conference, Malaysia, 28–30 September, 2011. find
  29. Khoja, S. ‘‘Stemming.” Pacific University.” Personal Academic Webpage http://zeus.cs.pacificu.edu/shereen/research.htm, (Accessed July 1, 2017). ↗
  30. Khoja, Shereen, Garside, Roger, 1999. Stemming arabic text. Computing Department, Lancaster University, Lancaster, UK. find
  31. Larkey, Leah S., Connell, Margaret E., 2006. Arabic information retrieval at UMass in TREC-10. Massachusetts Univ Amherst Center for Intelligent Information Retrieval. ↗
  32. Larkey, Leah S., Ballesteros, Lisa, Connell, Margaret E., 2002. Improving stemming for Arabic information retrieval: light stemming and co-occurrence analysis. Proceedings of the 25th annual international ACM SIGIR conference on Research and development in information retrieval. ACM, pp. 275–282. find
  33. El Mahdaouy, Abdelkader, Gaussier, Éric, El Alaoui, Saïd Ouatik, 2014. Exploring term proximity statistic for Arabic information retrieval. 2014 Third IEEE International Colloquium in Information Science and Technology (CIST). IEEE, pp. 272–277. find
  34. Murty, Vadali Srinivasa, Raj, P.C. Reghu, Raman, S., 2003. Design of a high-speed string matching co-processor for NLP. 2003 Proceedings 16th International Conference on VLSI Design. IEEE, pp. 183–188. find
  35. Nirenburg, Sergei., Wilks, Yorick., 2000. Machine translation. Adv. Comput. 52, 159– 188. find
  36. Qutrub, ‘‘ ﻝ ﺎ ﻌ ﻓ ﻷ ﺍ ﻒ ﻳ ﺮ ﺼ ﺗ ﺞ ﻣ ﺎ ﻧ ﺮ ﺑ : ﺏ ﺮ ﻄ ﻗ .” http://qutrub.arabeyes.org/index (Accessed July 1, 2017). ↗
  37. Rajhi, A., 1979. ‘ ﻲ ﻓ ﺮ ﺼ ﻟ ﺍ ﻖ ﻴ ﺒ ﻄ ﺘ ﻟ ﺍ ’ (Applied Morphology). Dar Al Nahda Al Arabeya for Publishing, Beirut, Lebanon. find
  38. Raman, S., Shaji, E.R., 1995. ASIC design of a matching unit for NLP. Microprocessors Microsys. 19 (6), 327–340. ↗
  39. Rasmussen, E., 1991. Introduction: parallel processing and information retrieval. Inf. Process. Manage. 27 (4), 255–263. ↗
  40. Ratha, Nalini K., Jain, Anil K., Rover, Diane T., 2000. FPGA-based coprocessor for text string extraction. Fifth IEEE International Workshop on Computer Architectures for Machine Perception. IEEE, pp. 217–221. find
  41. Saad, Elsayed M., Awadalla, Medhat H., Alajmi, Amal, 2010. Arabic verb pattern extraction. 2010 10th International Conference on Information Sciences Signal Processing and their Applications (ISSPA). IEEE, pp. 642–645. find
  42. Sawalha, Majdi, Atwell, E.S., 2008. Comparative evaluation of arabic language morphological analyzers and stemmers. In: Proceedings of COLING 2008 22nd International Conference on Computational Linguistics (Poster Volume), pp. 107–110. Coling 2008 Organizing Committee, 2008. find
  43. Sembok, Tengku Mohd T., Ata, Belal Abu, 2013. Arabic word stemming algorithms and retrieval effectiveness. Proceedings of the World Congress on Engineering, vol. 3, p. 1577. find
  44. Sensory, NLP-5x Natural Language Processor. http://www.sensory.com/products/integrated-circuits/nlp-5x-natural-language-processor/ (Accessed July 1, 2017). ↗
  45. Soudi, Abdelhadi, Neumann, Günter, Van den Bosch, Antal, 2007. Arabic computational morphology: knowledge-based and empirical methods. Arabic Computational Morphology. Springer, Netherlands, pp. 3–14. ↗
  46. Statista. ‘‘Social Media Statistics and Facts.” http://www.statista.com/topics/1164/social-networks/ (Accessed July 1, 2017). ↗
  47. Yaghi, Jim, Titchener, Mark R., Yagi, Sane, 2003. T-Code compression for Arabic computational morphology. Proceedings of the Australasian Language Technology Workshop, pp. 425–465. find
  48. Yagi, Sane M., Harous, Saad, 2003. Arabic morphology: an algorithm and statistics. Proceedings of the 2003 International Conference on Artificial Intelligence (IC-AI 2003). find
  49. Yang, Jieming, Liu, Yuanning, Zhu, Xiaodong, Liu, Zhen, Zhang, Xiaoxu., 2012. A new feature selection based on comprehensive measurement both in inter-category and intra-category for text categorization. Inf. Process. Manage. 48 (4), 741– 754. ↗

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/damaj-2019-parallel-hardware-faster-morphological-analysis/