Towards increasing F-measure of approximate string matching in O(1) complexity

Adrian Boguszewski; Julian Szymański; Karol Draszawka

doi:10.15439/2016e311

Towards increasing F-measure of approximate string matching in O(1) complexity

Abstract

The paper analyzes existing approaches for approximate string matching based on linear search with Levenshtein distance, AllScan and CPMerge algorithms using cosine, Jaccard and Dice distance measures. The methods are presented and compared to our approach that improves indexing time using Locally Sensitive Hashing. Advantages and drawbacks of the methods are identified based on theoretical considerations as well as empirical evaluations on real-life dictionaries.

Citations

0

CrossRef
0

Web of Science
0

Scopus

Authors (3)

Cite as

Full text

full text is not available in portal

full content of the article see on external site open in new tab

Keywords

Details

Category:: Conference activity
Type:: materiały konferencyjne indeksowane w Web of Science
Title of issue:: PROCEEDINGS OF THE 2016 FEDERATED CONFERENCE ON COMPUTER SCIENCE AND INFORMATION SYSTEMS (FEDCSIS) strony 527 - 532
ISSN:: 2325-0348
Language:: English
Publication year:: 2016
Bibliographic description:: Boguszewski A., Szymański J., Draszawka K..: Towards increasing F-measure of approximate string matching in O(1) complexity, W: PROCEEDINGS OF THE 2016 FEDERATED CONFERENCE ON COMPUTER SCIENCE AND INFORMATION SYSTEMS (FEDCSIS), 2016, IEEE,.
DOI:: Digital Object Identifier (open in new tab) 10.15439/2016e311
Verified by:: Gdańsk University of Technology