Simple, compact and robust approximate string dictionary

DOI10.1016/J.JDA.2014.08.003zbMATH Open1305.68380arXiv1312.4678OpenAlexW2044001676MaRDI QIDQ405575FDOQ405575

Authors: Ibrahim Chegrane, Djamal Belazzougui 

Publication date: 5 September 2014

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Abstract: This paper is concerned with practical implementations of approximate string dictionaries that allow edit errors. In this problem, we have as input a dictionary $D$ of $d$ strings of total length $n$ over an alphabet of size $sigma$. Given a bound $k$ and a pattern $x$ of length $m$, a query has to return all the strings of the dictionary which are at edit distance at most $k$ from $x$, where the edit distance between two strings $x$ and $y$ is defined as the minimum-cost sequence of edit operations that transform $x$ into $y$. The cost of a sequence of operations is defined as the sum of the costs of the operations involved in the sequence. In this paper, we assume that each of these operations has unit cost and consider only three operations: deletion of one character, insertion of one character and substitution of a character by another. We present a practical implementation of the data structure we recently proposed and which works only for one error. We extend the scheme to $2leqk<m$. Our implementation has many desirable properties: it has a very fast and space-efficient building algorithm. The dictionary data structure is compact and has fast and robust query time. Finally our data structure is simple to implement as it only uses basic techniques from the literature, mainly hashing (linear probing and hash signatures) and succinct data structures (bitvectors supporting rank queries).

Full work available at URL: https://arxiv.org/abs/1312.4678

Recommendations

• Efficient Approximate Dictionary Look-Up for Long Words over Small Alphabets
• String Processing and Information Retrieval
• A simple, fast, and compact static dictionary
• Approximate string matching with compressed indexes
• Compressed Indexes for Approximate String Matching
• Compressed indexes for approximate string matching
• Fast index for approximate string matching
• scientific article; zbMATH DE number 2011852
• Very fast and simple approximate string matching
• Fast and practical approximate string matching

zbMATH Keywords

edit distancehashingapproximate string matchingdictionary indexing

Mathematics Subject Classification ID

Approximation algorithms (68W25) Algorithms on strings (68W32)

Cites Work

• Dictionary matching and indexing with errors and don't cares
• Title not available (Why is that?)
• Compressed string dictionary look-up with edit distance one
• Faster and Space-Optimal Edit Distance “1” Dictionary
• Efficient randomized pattern-matching algorithms
• The Power of Simple Tabulation Hashing
• An algorithm for approximate membership checking with application to password security
• Title not available (Why is that?)
• Partial-Match Retrieval Algorithms
• Indexing methods for approximate dictionary searching, comparative analysis

Cited In (4)

• Index structures for fast similarity search for binary vectors
• Fast approximate search in large dictionaries
• Index structures for fast similarity search for symbol strings
• Faster and Space-Optimal Edit Distance “1” Dictionary

This page was built for publication: Simple, compact and robust approximate string dictionary

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q405575)