Publikace detail

Fast and Precise Convolutional Jaro and Jaro-Winkler Similarity

Autoři: Rozinek Ondřej | Mareš Jan

Rok: 2024

Druh publikace: článek ve sborníku

Název zdroje: Proceedings of the 35th Conference of Open Innovations Association FRUCT

Název nakladatele: IEEE (Institute of Electrical and Electronics Engineers)

Místo vydání: New York

Strana od-do: 604-613

Tituly:

Jazyk	Název	Abstrakt	Klíčová slova
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

Vyhledávání

Přihlášení pro studenty

Přihlášení pro zaměstnance

Publikace detail

Katedry

Služby

Jak nás najdete?

Často hledáte