SoftMatcha: A Soft and Fast Pattern Matcher for Billion-Scale Corpus Searches

• URL: http://arxiv.org/abs/2503.03703v1
• Date: Wed, 05 Mar 2025 17:53:11 GMT
• Title: SoftMatcha: A Soft and Fast Pattern Matcher for Billion-Scale Corpus Searches
• Authors: Hiroyuki Deguchi, Go Kamoda, Yusuke Matsushita, Chihiro Taguchi, Kohei Suenaga, Masaki Waga, Sho Yokoi,
• Abstract summary: We propose a novel algorithm that achieves semantic yet efficient pattern matching by relaxing a surface-level matching with word embeddings.<n>Our experiments demonstrate that the proposed method can execute searches on billion-scale corpora in less than a second.
• Score: 5.80278230280824
• License: http://creativecommons.org/licenses/by/4.0/
• 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 \emph{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.

Related papers

• A General and Flexible Multi-concept Parsing Framework for Multilingual Semantic Matching [60.51839859852572]
  We propose to resolve the text into multi concepts for multilingual semantic matching to liberate the model from the reliance on NER models. We conduct comprehensive experiments on English datasets QQP and MRPC, and Chinese dataset Medical-SM.
  arXiv  Detail & Related papers  (2024-03-05T13:55:16Z)
• Dense X Retrieval: What Retrieval Granularity Should We Use? [56.90827473115201]
  Often-overlooked design choice is the retrieval unit in which the corpus is indexed, e.g. document, passage, or sentence. We introduce a novel retrieval unit, proposition, for dense retrieval. Experiments reveal that indexing a corpus by fine-grained units such as propositions significantly outperforms passage-level units in retrieval tasks.
  arXiv  Detail & Related papers  (2023-12-11T18:57:35Z)
• Beyond Contrastive Learning: A Variational Generative Model for Multilingual Retrieval [109.62363167257664]
  We propose a generative model for learning multilingual text embeddings. Our model operates on parallel data in $N$ languages. We evaluate this method on a suite of tasks including semantic similarity, bitext mining, and cross-lingual question retrieval.
  arXiv  Detail & Related papers  (2022-12-21T02:41:40Z)
• On The Ingredients of an Effective Zero-shot Semantic Parser [95.01623036661468]
  We analyze zero-shot learning by paraphrasing training examples of canonical utterances and programs from a grammar. We propose bridging these gaps using improved grammars, stronger paraphrasers, and efficient learning methods. Our model achieves strong performance on two semantic parsing benchmarks (Scholar, Geo) with zero labeled data.
  arXiv  Detail & Related papers  (2021-10-15T21:41:16Z)
• A Simple and Efficient Probabilistic Language model for Code-Mixed Text [0.0]
  We present a simple probabilistic approach for building efficient word embedding for code-mixed text. We examine its efficacy for the classification task using bidirectional LSTMs and SVMs.
  arXiv  Detail & Related papers  (2021-06-29T05:37:57Z)
• Intrinsic Probing through Dimension Selection [69.52439198455438]
  Most modern NLP systems make use of pre-trained contextual representations that attain astonishingly high performance on a variety of tasks. Such high performance should not be possible unless some form of linguistic structure inheres in these representations, and a wealth of research has sprung up on probing for it. In this paper, we draw a distinction between intrinsic probing, which examines how linguistic information is structured within a representation, and the extrinsic probing popular in prior work, which only argues for the presence of such information by showing that it can be successfully extracted.
  arXiv  Detail & Related papers  (2020-10-06T15:21:08Z)
• Interactive Extractive Search over Biomedical Corpora [41.72755714431404]
  We present a system that allows life-science researchers to search a linguistically annotated corpus of texts. We introduce a light-weight query language that does not require the user to know the details of the underlying linguistic representations. Search is performed at an interactive speed due to efficient linguistic graph-indexing and retrieval engine.
  arXiv  Detail & Related papers  (2020-06-07T13:26:32Z)
• Syntactic Search by Example [44.69040040007045]
  We present a system that allows a user to search a large linguistically annotated corpus using syntactic patterns over dependency graphs. We introduce a light-weight query language that does not require the user to know the details of the underlying syntactic representations. Search is performed at an interactive speed due to an efficient linguistic graph-indexing and retrieval engine.
  arXiv  Detail & Related papers  (2020-06-04T16:59:01Z)
• A Corpus for Large-Scale Phonetic Typology [112.19288631037055]
  We present VoxClamantis v1.0, the first large-scale corpus for phonetic typology. aligned segments and estimated phoneme-level labels in 690 readings spanning 635 languages, along with acoustic-phonetic measures of vowels and sibilants.
  arXiv  Detail & Related papers  (2020-05-28T13:03:51Z)
• Language-Independent Tokenisation Rivals Language-Specific Tokenisation for Word Similarity Prediction [12.376752724719005]
  Language-independent tokenisation (LIT) methods do not require labelled language resources or lexicons. Language-specific tokenisation (LST) methods have a long and established history, and are developed using carefully created lexicons and training resources. We empirically compare the two approaches using semantic similarity measurement as an evaluation task across a diverse set of languages.
  arXiv  Detail & Related papers  (2020-02-25T16:24:42Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.