首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >需要一些关于字符串匹配算法的信息吗?

问需要一些关于字符串匹配算法的信息吗?
EN

Data Science用户
提问于 2020-01-10 09:33:47
回答 3查看 109关注 0票数 1

让我解释一个场景来更好地解释我的问题

假设我在一家与信用卡有关的公司工作,每个月人们都会上传他们的收据,我想看看那个人是否买了水果。让我们假设我们使用OCR只提取购买并存储在列表中的项目的名称。

我做的第一件事就是在网上刮起到处都是水果的名字,然后把它们的名字存储在一个大的文本文件中。

现在,我想知道如何匹配/查找,并作出决定,该人购买水果。

( 1)对大量数据进行搜索/匹配的算法。

我只是在寻求关于在这种场景中实现什么的建议。提前谢谢。

EN

回答 3

Data Science用户

发布于 2020-02-09 15:56:45

首先,尝试最简单的方法--确定性检查,寻找水果名称集和购买物品集之间的交叉重叠。

集合比较是可伸缩的,因为每个项的查找时间都是恒定的。

如果缩放是常规集合成员资格检查的一个问题,则布卢姆滤波器是一个选项。

票数 1
EN

Data Science用户

发布于 2020-01-10 09:42:14

对于字符串匹配,我通常使用水母库。如果要计算两个水果之间的字符串相似性(检查哪一个相似),可以使用Levenshtein。在文档这里中有更多的方法。

Levenshtein距离

Levenshtein距离表示将一个单词改为另一个单词所需的插入、删除和补贴的数量。

票数 0
EN

Data Science用户

发布于 2020-02-09 15:09:39

用于此用例的默认算法之一(将在文本中同时搜索的一组搜索字符串)是阿霍·科拉西克。在维基百科页面上:“算法的复杂性与字符串的长度、搜索文本的长度和输出匹配的数量成线性关系。”该算法在所有常用编程语言中都有实现。如果这不够有效,您将需要使用某种哈希技巧来获得更快的性能。

票数 0
EN
页面原文内容由Data Science提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://datascience.stackexchange.com/questions/66256

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档