计算Jaro相似性的快速算法
Joyanta Basak1, Nidhibahen Shah1, Kenneth Haase2
1School of Computing, University of Connecticut, Storrs, Connecticut, USA.
概括
我们增强了Jaro和Jaro-Winkler相似性算法,以更快地进行字符串比较. 新方法显著降低了计算成本,特别是在大型数据集和记录链接中的重复比较方面.
科学领域:
- 计算机科学 计算机科学
- 数据科学数据科学数据科学
- 计算语言学 计算语言学
背景情况:
- Jaro 和 Jaro-Winkler 的相似性是基于字符的字符串比较的关键.
- 传统方法具有高的计算成本,限制了大规模应用.
- 之前的工作引入了长字符串的线性时间Jaro相似性算法.
研究的目的:
- 为Jaro和Jaro-Winkler相似性引入增强的算法.
- 为了提高短串和长串的运行时间效率.
- 为了减少大规模,重复的字符串比较的计算时间.
主要方法:
- 针对Jaro和Jaro-Winkler相似性的优化算法的开发.
- 实施技术,以有效处理较短的绳子.
- 引入方法来大大减少自比较场景中的计算.
主要成果:
- 与传统方法相比,增强的算法显示了更好的运行时性能.
- 新的算法对短字符串和长字符串都有效.
- 对于大数据集和重复的字符串比较,实现了显著的加快速度.
结论:
- 增强的Jaro和Jaro-Winkler算法提供了实质性的计算改进.
- 这些进步使算法更适合大规模记录链接和实体解析.
- 优化的方法解决了传统的弦比较技术的局限性.
相关概念视频
Wilcoxon Signed-Ranks Test for Matched Pairs
555
The Wilcoxon signed-rank test for matched pairs evaluates the null hypothesis by combining the ranks of differences with their signs. It essentially tests whether the median of the differences in a population of matched pairs is zero. Since the test incorporates more information than the sign test, it generally yields more trustable conclusions. This test also does not require the data to follow a normal distribution, but two conditions must be met for it to be applicable: (1) the data must...
555
Routh-Hurwitz Criterion II
1.1K
In the application of the Routh-Hurwitz criterion, two specific scenarios can arise that complicate stability analysis.
The first scenario occurs when a singular zero appears in the first column of the Routh table. This situation creates a division by zero issues. To resolve this, a small positive or negative number, denoted as epsilon (∈), is substituted for the zero. The stability analysis proceeds by assuming a sign for ∈. If ∈ is positive, any sign change in the first...
The first scenario occurs when a singular zero appears in the first column of the Routh table. This situation creates a division by zero issues. To resolve this, a small positive or negative number, denoted as epsilon (∈), is substituted for the zero. The stability analysis proceeds by assuming a sign for ∈. If ∈ is positive, any sign change in the first...
1.1K
Routh-Hurwitz Criterion I
642
Consider an electrical power grid, where stability is essential to prevent blackouts. The Routh-Hurwitz criterion is a valuable tool for assessing system stability under varying load conditions or faults. By analyzing the closed-loop transfer function, the Routh-Hurwitz criterion helps determine whether the system remains stable.
To apply the Routh-Hurwitz criterion, a Routh table is constructed. The table's rows are labeled with powers of the complex frequency variable s, starting from the...
To apply the Routh-Hurwitz criterion, a Routh table is constructed. The table's rows are labeled with powers of the complex frequency variable s, starting from the...
642
Causes of Similarity-Dissimilarity Effect
308
The similarity-dissimilarity effect, a fundamental concept in social psychology, explains how interpersonal similarities and differences influence attraction and social interactions. This effect is supported by three key psychological perspectives: balance theory, social comparison theory, and consensual validation.Balance Theory and Cognitive ConsistencyBalance theory, developed by Fritz Heider, posits that individuals seek cognitive consistency in their relationships. When two people share...
308
One-Compartment Open Model: Wagner-Nelson and Loo Riegelman Method for ka Estimation
1.3K
This lesson introduces two critical methods in pharmacokinetics, the Wagner-Nelson and Loo-Riegelman methods, used for estimating the absorption rate constant (ka) for drugs administered via non-intravenous routes. The Wagner-Nelson method relates ka to the plasma concentration derived from the slope of a semilog percent unabsorbed time plot. However, it is limited to drugs with one-compartment kinetics and can be impacted by factors like gastrointestinal motility or enzymatic degradation.
On...
On...
1.3K
Wilcoxon Signed-Ranks Test for Median of Single Population
489
The Wilcoxon signed-rank test for the median of a single population is a nonparametric test used to evaluate whether the median of a population differs from a specified value. Unlike parametric tests, it does not require data to follow a normal distribution, making it suitable for non-normal or small samples. The test begins by calculating the difference (d) between each observation and the hypothesized median. The absolute values of these differences are ranked in ascending order, with ties...
489


