Top-k String Auto-Completion with Synonyms
Auto-completion is one of the most prominent features of modern information systems. The existing solutions of auto-completion provide the suggestions based on the beginning of the currently input character sequence (i.e. prefix). However, in many real applications, one entity often has synonyms or abbreviations. For example, "DBMS" is an abbreviation of "Database Management Systems". In this paper, we study a novel type of auto-completion by using synonyms and abbreviations. We propose three trie-based algorithms to solve the top-k auto-completion with synonyms; each one with different space and time complexity trade-offs. Experiments on large-scale datasets show that it is possible to support effective and efficient synonym-based retrieval of completions of a million strings with thousands of synonyms rules at about a microsecond per-completion, while taking small space overhead (i.e. 160-200 bytes per string). The source code of our experiments can be download at: http://udbms.cs.helsinki.fi/?projects/autocompletion/download .
Code (0)
등록된 구현이 없습니다.
Tasks
ManagementRetrievalSimilar Papers 제목 키워드 기반
Automatic Synonym Discovery with Knowledge Bases
Recognizing entity synonyms from text has become a crucial task in many entity-leveraging applications. However, discovering entity synonyms from domain-specific text corpora (e.g., news articles, scientific papers) is r…
ArticlesIt Runs in the Family: Searching for Synonyms Using Digitized Family Trees
Searching for a person's name is a common online activity. However, Web search engines provide few accurate results to queries containing names. In contrast to a general word which has only one correct spelling, there ar…
InfoLM: A New Metric to Evaluate Summarization & Data2Text Generation
Assessing the quality of natural language generation systems through human annotation is very expensive. Additionally, human annotation campaigns are time-consuming and include non-reusable human labour. In practice, res…
Language ModelingLanguage ModellingText GenerationGenerating and Scoring Correction Candidates in Chinese Grammatical Error Diagnosis
Grammatical error diagnosis is an essential part in a language-learning tutoring system. Based on the data sets of Chinese grammar error detection tasks, we proposed a system which measures the likelihood of correction c…
Decision MakingSentenceFrom Context to Intent: Reasoning-Guided Function-Level Code Completion
The growing capabilities of Large Language Models (LLMs) have led to their widespread adoption for function completion within code repositories. Recent studies on such tasks show promising results when explicit instructi…
Code Completion