SoftMatcha: A Soft and Fast Pattern Matcher for Billion-Scale Corpus Searches
Hiroyuki Deguchi, Go Kamoda, Yusuke Matsushita, Chihiro Taguchi, Kohei Suenaga, Masaki Waga, Sho Yokoi · 2025
Read SoftMatcha: A Soft and Fast Pattern Matcher for Billion-Scale Corpus Searches by Hiroyuki Deguchi, Go Kamoda, Yusuke Matsushita, Chihiro Taguchi, Kohei Suenaga, Masaki Waga, Sho Yokoi (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-03703.txt.
Introduction
Hiroyuki Deguchi and co-authors build a pattern matcher that finds meaning, not just exact strings, across billion-scale text sets, in work from 2025. Corpus workers lean on string tools and context lists to study real language use. Those tools miss spelling variants and rewordings.
Vector search catches meaning but often returns texts that share a topic, not the pattern. Their method loosens string matching with word vectors, so near matches with shifted wording still hit. Inverted index tricks keep it fast at huge scale. A web tool makes it open to all. Tests show sharp, quick searches where plain tools either miss cases or flood back near misses on topic alone.
Catalog record
| CREATOR | Hiroyuki Deguchi, Go Kamoda, Yusuke Matsushita, Chihiro Taguchi, Kohei Suenaga, Masaki Waga, Sho Yokoi |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 52 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2503-03703
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
SoftMatcha: A Soft and Fast Pattern Matcher for Billion-Scale Corpus Searches Hiroyuki Deguchi, Go Kamoda, Yusuke Matsushita, Chihiro Taguchi, Kohei Suenaga, Masaki Waga, Sho Yokoi Abstract Researchers and practitioners in natural language processing and computational linguistics frequently observe and analyze the real language usage in large-scale corpora. For that purpose, they often employ off-the-shelf pattern-matching tools, such as grep , and keyword-in-context concordancers, which is widely used in corpus linguistics for gathering examples. Nonetheless, these existing techniques rely on surface-level string matching, and thus they suffer from the major limitation of not being able to handle orthographic variations and paraphrasing—notable and common phenomena in any natural language. In addition, existing continuous approaches such as dense vector search tend to be overly coarse, often retrieving texts that are unrelated but share similar topics. Given these challenges, we propose a novel algorithm that achieves soft (or semantic) yet efficient pattern matching by relaxing a surface-level matching with word embeddings. Our algorithm is highly scalable with respect to the size of the corpus text utilizing inverted indexes. We have prepared an efficient implementation, and we provide an accessible web tool. Our experiments demonstrate that the proposed method (i) can execute searches on billion-scale corpora in less than a second, which is comparable in speed to surface-level string matching and dense vector search; (ii) can extract harmful instances that semantically match queries from a large set of English and Japanese Wikipedia articles; and (iii) can be effectively applied to corpus-linguistic analyses of Latin, a language with highly diverse inflections. \lingset aboveglftskip=-1.6ex, belowglpreambleskip=0ex, aboveexskip=0ex plus .1ex minus .1ex, belowexskip=0ex \CJKencfamily UTF8mc 1 Introduction Recent advances in natural language processing (NLP) and corpus linguistics are largely driven by the availability of massive text corpora ( Gao et al., 2020 ; Biderman et al., 2023b ; Raffel et al., 2019 ; Van Der Zwaan et al., 2017 ; Mcgillivray et al., 2020 ) . The field of NLP, driven by the grand goal of building intelligent chatbots and machine translation systems, has achieved remarkable breakthroughs over the past decade, largely thanks to self-supervised representation learning from vast corpora ( Mikolov et al., 2013 ; Pennington et al., 2014 ; Devlin et al., 2019a ; Radford et al., 2019 ) . Notable causal language models (LMs), capable of passing high-stakes exams ( Katz et al., 2024 ; OpenAI, 2024 ; Jung et al., 2023 ) , serving as general-purpose problem solvers ( Brown et al., 2020 ) , and engaging in realistic conversations with beloved characters ( De Freitas, 2023 ; Chen et al., 2024 ) , owe their foundational abilities to next-token prediction learned from large-scale data ( Brown et al., 2020 ; Dubey et al., 2024 ; Riviere et al., 2024 ) . In corpus linguistics ( McEnery & Hardie, 2011 ) , computational linguistics ( Jurafsky & Martin, 2024 ) , and digital humanities ( Jensen, 2014 ) —disciplines aiming to uncover the scientific and computational principles of human language—such vast linguistic resources, consisting of the language use itself, have become more indispensable than ever in this era of large-scale corpora ( Van Der Zwaan et al., 2017 ; Mcgillivray et al., 2020 ) . Given this context, the demand for efficient pattern matchers that enable rapid searches across massive corpora is higher than ever ( Liu et al., 2024 ; Smadja, 1993 ) . For example, when harmful information, misinformation, or memorized privacy information is generated by a large LM, it is necessary to identify the corresponding training instances where this information originated ( Guo et al., 2022 ; Wang et al., 2024c ; Ippolito et al., 2023 ; Biderman et al., 2023a ) . Another example is when researchers wish to determine which of two linguistic phenomena of interest is more frequent; conducting exhaustive searches across the largest available corpora is essential ( Biber, 2015 ) for this purpose. Notably, many linguistic phenomena—word frequency as a simple example—follow a power-law distribution ( Zipf, 1951 ; Heap, 1980 ; Kobayashi & Tanaka-Ishii, 2018 ) . Consequently, only with vast corpora can we observe and analyze the various rare events residing in the long tail, which constitute the majority of linguistic phenomena. Pattern Theorem 1 John was born in Hard matching \cdots thanks to Theorem 1 \cdots \cdots John was born in 1345 \cdots (e.g., grep ) Soft matching \cdots thanks to Theorem 1 \cdots \cdots John was born in 1345 \cdots ( ours ) \cdots Theorem 3 holds because \cdots \cdots Edward had died in May 1910 \cdots \cdots By Lemma 5 , we may assume \cdots \cdots Robert was born in England \cdots \cdots Equation 1 describes \cdots \cdots the Emperor Henry, died in 1125 \cdots Table 1: Hard pattern matching (e.g., grep ) and soft pattern matching (our method). Hard matching is based on surface-level comparison and does not match if, e.g., a synonym is used; Soft matching is based on semantic comparison and robust to such variations thanks to word embeddings. One of the challenges when working with large corpora is that pattern-matching tools based on string matching ( Hakak et al., 2019 ) , such as grep ( Bambenek & Klus, 2009 ) and ripgrep ( Gallant, 2024 ) , or linguist-oriented tools often referred to as KWIC ( Anthony, 2013 ; Culy & Lyding, 2010 ; Schweinberger, 2024 ) , primarily rely on surface-level exact matching as their core strategy. Because natural languages are characterized by their flexibility and richness in how humans can express similar concepts in different ways ( McKeown, 1979 ; Witteveen & Andrews, 2019 ; Ganitkevitch et al., 2013 ) , strictly exact string matching may not meet users’ demands. For example, on top of the query word in standard spelling, it is often desirable to catch non-standard spellings as well, such as how r u instead of how are you , which are widespread particularly on the web and in texting ( Schulz, 2018 ) . Additionally, it is also desirable to catch different inflected word forms such as sing , sang , sung , sings , and singing , which differ only in their morphological features and share the same lemma (base form) ( Don, 2014 ; Embick, 2015 ) . Rule-based exact matching is particularly hard when the target language is morphologically complex and exhibits irregular inflectional patterns. To resolve the mismatch between the symbolic nature of existing pattern matchers and the diverse orthographic and morphological variations inherent in natural language, we have developed a soft (or semantic) yet efficient pattern matcher ( Section 3 ). The core strategy is based on the simple idea of softening the matching process from binary \{0,1\} values to continuous values, using word embeddings. By adopting inverted indexes and several other techniques, our tool can enumerate all softly matching instances in billion-scale corpora in less than a second. Table 1 shows specific examples of its operation. Our proposed method is capable not only of enumerating exact matches but also of flexibly listing semantically similar instances, even when their surface forms differ. For example, given the query “ Theorem 1 ”, the method can retrieve instances such as “ Lemma 5 ”. This characteristic substantially enhances key