首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >NLP -改进模糊字符串匹配的运行时间和召回率

问NLP -改进模糊字符串匹配的运行时间和召回率
EN

Stack Overflow用户
提问于 2012-04-24 09:33:29
回答 1查看 369关注 0票数 0

我已经做了一个有效的算法,但是运行时间非常可怕。是的,我从一开始就知道这将是可怕的,但不会那么严重。对于只有200000条记录的情况,该程序运行超过一个小时。

基本上我要做的是:

代码语言:javascript
复制
for each searchfield in search fields
    for each sample in samples
        do a q-gram matching
    if there are matches then return it
    else
        split the searchfield into uniwords
        for each sample in samples
            split sample into uniwords
            for each uniword in samples
                if the uniword is a known abbreviation
                    then search the dictionary for its full word or other known abbr
                else do a jaro-winkler matching
            average the distances of all the uniwords
            if the average is above threshold then make it as a match and break
        end for
        if there is a match make a comment that it matched one of the samples partially
    end else
end for

是的,这段代码非常适合循环。我使用暴力是因为召回是非常重要的。所以,我想知道如何才能让它更快,因为我不仅运行它的200000数据的数百万数据和客户端的计算机不是高端(1 1GB 2 1GB的Ram奔腾4或双核,我测试这个程序的计算机是双核的4 1GB的Ram)。我遇到了TF/IDF,但我不知道它是否足够。我想知道谷歌如何才能进行实时搜索。

提前感谢!

编辑:这个程序是一个数据过滤器。从200,000个虚拟数据(实际数据大约是12M)中,我必须过滤与样本无关的数据(500个虚拟样本,我仍然不知道实际有多少样本)。

使用给定的虚拟数据和样本,运行时间大约为1小时,但在这里和那里修补后,我已经成功地将其减少到10-15分钟。我通过对以相同字符开头的字段和样本进行分组(不考虑特殊和无意义的单词,例如,a,an),并将字段与具有相同第一个字符的样本进行匹配,从而减少了它。我知道这里面有问题。如果字段的第一个字符拼写错误,该怎么办?但我认为这样的数量可以忽略不计。样本的拼写是正确的,因为它总是得到维护。

EN

回答 1

Stack Overflow用户

发布于 2012-05-04 04:43:11

你的编程语言是什么?我想使用q=2或3就足够了。我还建议从大学到更高的学位。

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

https://stackoverflow.com/questions/10290626

复制
相关文章

相似问题

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