Back to Patterns: Efficient J apanese Morphological Analysis with Feature-Sequence Trie (2023)

Abstract: Accurate neural models are much less efficient than non-neural models and are useless for processing billions of social media posts or handling user queries in real time with a limited budget. This study revisits the fastest pattern-based NLP methods to make them as accurate as possible, thus yielding a strikingly simple yet surprisingly accurate morphological analyzer for Japanese. The proposed method induces reliable patterns from a morphological dictionary and annotated data. Experimental results on two standard datasets confirm that the method exhibits comparable accuracy to learning-based baselines, while boasting a remarkable throughput of over 1,000,000 sentences per second on a single modern CPU. The source code is available at https://www.tkl.iis.u-tokyo.ac.jp/ynaga/jagger/

## introduction the amount of text data being processed has greatly increased since the advent of communication platforms such as twitter, zoom, and slack, and nlp services such as deepl and grammarly have millions of users. some users analyze textual big data for marketing, linguistics, or sociology, while others deploy nlp services on their own devices because of privacy concerns. it is therefore becoming important to develop highly efficient methods to process massive text data and user queries with limited computational resources. however, the recent campaign for efficient nlp does not focus on literally efficient methods that scale to increasing data sizes and run on resourceconstrained devices. instead, most "efficient" nlp studies @xcite focus on neural methods, which are too slow to handle billions of social media posts and too large to deploy on edge devices. those studies seek to make model training or inference relatively efficient within the deep learning framework. thus, the large efficiency gap with respect to classical methods has never been filled. in this study, i take an orthogonal approach toward absolutely efficient nlp by seeking to boost the accuracy of the fastest methods. specifically, i have developed a remarkably simple yet accurate method for japanese morphological analysis, which is a joint task of word segmentation, part-of-speech (pos) tagging, and lemmatization. this method revisits the classical longest matching method; it greedily applies patterns that determine the next position to segment and then identifies the pos tag for the segmented word, as illustrated in figure 1 . to obtain reliable patterns, starting from words in a morphological dictionary and training data, patterns are extended with posterior surface contexts and previous pos tags, and the patterns' segmentation offsets and tags are determined by frequency. the extracted patterns are then stored in an efficient double-array trie @xcite . the proposed method was evaluated on two standard corpora @xcite . the experimental results confirmed that this simple method can process 1,000,000 sentences per second on an m2 macbook air, with comparable accuracy to learning-based baselines @xcite . algorithm 1 pattern-based morphological analysis input: sequence of characters, c; set of patterns stored in trie, @xmath0, shift, t)} output: sequence of words with tags @xmath1, tj)} 1: i ← 0 2: while @xmath2: ( ŝhift, t) = longest_prefix_search(@xmath3, p) 4: append(s, (c i+ ŝhift i , t)) 5: i ← i + ŝhift 6: return s ## pattern-based morphological analysis this section describes the method of japanese morphological analysis used here, which performs word segmentation, pos tagging, and lemmatization. to maximize the tagging efficiency, i return to a pattern-based algorithm that is similar to the longest matching algorithm @xcite . the longest matching algorithm performs deterministic word segmentation by using a dictionary. starting from the beginning of the input, it greedily finds the longest dictionary words to segment the input. although this simple algorithm exhibits moderate accuracy in chinese and japanese with transformation rules @xcite @xcite , there is a gap in accuracy from search-and classification-based approaches @xcite . to make search-based morphological analysis partially deterministic, @xcite extracted surface patterns from tagging results; however, the speed-up factor was at most 1.5. ## experiments this section describes an experimental evaluation of the pattern-based morphological analyzer on two annotated corpora in different domains @xcite . the method was compared with two learning-based baselines @xcite in terms of efficiency and accuracy. note that all language resources and software used in the experiments are publicly available and free for academic use. ## conclusions this study sought to improve the accuracy of speedoriented, pattern-based methods for japanese morphological analysis, rather than improving the speed of accuracy-oriented neural models. the proposed method extracts pos-augmented patterns from a morphological dictionary and annotated data. experimental results on two standard datasets confirmed that this method achieves accuracy comparable to that of learning-based methods, with a very fast throughput of over 1,000,000 sentences per second on a laptop. i plan to apply this approach to other languages and even to other nlp tasks by discretizing the continuous representations induced by neural models to obtain patterns. the source code is released with gpl, lgpl, and 2-clause bsd licenses. message to researchers because the accuracies on nlp benchmark datasets are becoming saturated with a larger foundation model, researchers may want to set diverse goals based on underrepresented metrics besides accuracy (e.g., efficiency). i hope that this study will initiate serious research on speed-intensive approaches to nlp that can meet industry demands and enable researchers with limited computational resources to exert their ability.