Login for students

Login for employees

Publication detail

Fast and Precise Convolutional Jaro and Jaro-Winkler Similarity
Authors: Rozinek Ondřej | Mareš Jan
Year: 2024
Type of publication: článek ve sborníku
Name of source: Proceedings of the 35th Conference of Open Innovations Association FRUCT
Publisher name: IEEE (Institute of Electrical and Electronics Engineers)
Place: New York
Page from-to: 604-613
Titles:
Language Name Abstract Keywords
cze Rychlá a přesná konvoluční Jaro a Jaro-Winklerova podobnost V oblasti přibližného porovnávání řetězců na základě znaků zůstaly dominantní editační vzdálenosti, jako je Levenshteinova vzdálenost, a to i přes jejich kvadratickou časovou složitost. Tato skutečnost podnítila přijetí efektivnějších metrik, jako jsou Jaro a Jaro-Winkler. Tyto metody však často přehlížejí význam pořadí znaků v rámci okna přiřazování, což může nepříznivě ovlivnit přesnost. poprvé představujeme novou třídu algoritmů pro přibližné přiřazování řetězců na základě znaků, které využívají konvoluční jádro a překonávají výkonnost stávajících nejmodernějších algoritmů pro přibližné přiřazování řetězců na základě znaků bez dohledu. Tento článek představuje konvoluční Jaro (ConvJ) a konvoluční Jaro-Winkler (ConvJW), inovativní metriky podobnosti navržené k překonání těchto nedostatků. ConvJ a ConvJW využívají konvoluční přístup s Gaussovým vážením k efektivnímu zachycení polohové blízkosti odpovídajících znaků, což vede k přesnějšímu vyhodnocení podobnosti. Tato metoda nejenže dosahuje výpočetní účinnosti srovnatelné s metodami Jaro a Jaro-Winkler, ale také překonává nejmodernější technologie, pokud jde o skóre F1, a vykazuje rychlejší časy provedení ve srovnání s konvenčními implementacemi Jaro a Jaro-Winkler v různých souborech dat. Naše rozsáhlá experimentální analýza poukazuje na výjimečný výkon ConvJ a ConvJW v celé řadě datových sad. Pozoruhodné je, že ConvJ vykazuje 7x rychlejší dobu provádění než rychlá implementace Jaro a překonává nejmodernější skóre F1 s výraznou rezervou o 10 % vyšší než Jaro. Stanovením nového měřítka v oblasti přibližného porovnávání řetězců na základě znaků bez dohledu ukazuje náš výzkum novou cestu pro budoucí zkoumání a vývoj v této oblasti. Algoritmy ConvJ a ConvJW, které se vyznačují kvazilineární časovou složitostí a zvýšenou přesností, poskytují pevný základ pro rozvoj technik porovnávání řetězců. Tento vývoj je příslibem pro široké spektrum aplikací v oblasti dolování dat, bioinformatiky a příbuzných oblastech. Výpočetní účinnost;Konvoluce;Dolování dat;Algoritmy pro vyhledávání řetězců
eng Fast and Precise Convolutional Jaro and Jaro-Winkler Similarity In the domain of character-based approximate string matching, edit distances such as Levenshtein have remained predominant despite their quadratic time complexity. This reality has prompted the adoption of more efficient metrics like Jaro and Jaro-Winkler. However, these methods often overlook the significance of character order within the matching window, which can adversely affect accuracy.For the first time, we introduce a novel class of character-based approximate string matching algorithms that leverage a convolutional kernel, surpassing the performance of existing state-of-the-art unsupervised character-based approximate string matching algorithms. This paper presents Convolutional Jaro (ConvJ) and Convolutional Jaro-Winkler (ConvJW), innovative similarity metrics designed to overcome these shortcomings. ConvJ and ConvJW utilize a convolutional approach with Gaussian weighting to effectively capture the positional proximity of matching characters, resulting in a more precise similarity evaluation. This method not only achieves computational efficiency comparable to that of Jaro and Jaro-Winkler but also surpasses the state-of-the-art in terms of F1-score, demonstrating faster execution times compared to the conventional Jaro and Jaro-Winkler implementations across various datasets.Our extensive experimental analysis highlights the exceptional performance of ConvJ and ConvJW across a range of datasets. Remarkably, ConvJ exhibits a 7x faster execution time than the fast Jaro implementation and exceeds the state-of-the-art F1-score by a significant margin of 10% more than Jaro. By setting a new benchmark in unsupervised character-based approximate string matching, our research shows the new way for future exploration and development in this field. The ConvJ and ConvJW algorithms, characterized by their quasilinear time complexity and improved accuracy, provide a solid foundation for the advancement of string matching techniques. These developments hold promise fo Computational efficiency;Convolution;Data mining;String searching algorithms

Department

Map

en.mapy.cz

Services

Popular Links

© 2023 University of Pardubice, Studentská 95, 532 10 Pardubice 2
Phone: +420 466 036 111, 466 036 112, 466 036 113
Webmaster, RSS
Data box ID: f5vj9hu
Accessibility Statement
CC BY-NC-ND 4.0Creative CommonsAttributionNonCommercialNoDerivatives