标签: similarity

我试图围绕Bitap算法,但我无法理解算法步骤背后的原因.

我理解算法的基本前提,即(如果我错了,请纠正我):

Two strings:     PATTERN (the desired string)
                 TEXT (the String to be perused for the presence of PATTERN)

Two indices:     i (currently processing index in PATTERN), 1 <= i < PATTERN.SIZE
                 j (arbitrary index in TEXT)

Match state S(x): S(PATTERN(i)) = S(PATTERN(i-1)) && PATTERN[i] == TEXT[j], S(0) = 1

在英语术语中,PATTERN.substring(0,i) 如果前一个子字符串PATTERN.substring(0, i-1)成功匹配且字符at与字符at PATTERN[i]相同,则匹配TEXT的子字符串TEXT[j].

我不明白的是这个位移实现.详细介绍这个算法的官方文章基本上已经解决了,但我似乎无法想象应该发生什么. 算法规范只是本文的前两页,但我将重点介绍重要部分:

以下是该概念的位移版本:

以下是样本搜索字符串的T [text]:

这是一个算法的痕迹.

具体来说,我不明白T表的含义,以及OR当前状态下输入的原因.

如果有人能帮我理解到底发生了什么,我将不胜感激

我正在做一个社区网站,要求我计算任何两个用户之间的相似性.使用以下属性描述每个用户:

年龄,皮肤类型(油性,干性),头发类型(长,短,中),生活方式(活跃的户外爱好者,电视垃圾)等.

任何人都可以告诉我如何解决这个问题或指向我一些资源？

我在Lucene建了一个索引.我希望不指定查询,只是为了获得索引中两个文档之间的分数(余弦相似度或其他距离？).

例如,我从之前打开的IndexReader获取带有ID 2和4的文档.文档d1 = ir.document(2); 文件d2 = ir.document(4);

如何获得这两个文档之间的余弦相似度？

谢谢

我会解释我的问题:

我有一个名为的数据库表country.它有两列:ID和name.

当我想要搜索'paris',但拼错字:'pares'('e'代替'i'),我不会得到任何DB结果.

我希望系统能够提出可能有助于搜索的类似单词.

因此,我正在寻找帮助编写一个脚本,该脚本从DB中提出包含类似词语的建议:paris,paredes,...等.

我已经教过一些用Python进行文本挖掘的入门课程,并且该课程尝试了与提供的练习文本类似的方法.有些学生对text1.similar()的结果与其他学生不同.

所有版本等都是一样的.

有谁知道为什么会出现这些差异？谢谢.

在命令行使用的代码.

python
>>> import nltk
>>> nltk.download() #here you use the pop-up window to download texts
>>> from nltk.book import *
*** Introductory Examples for the NLTK Book ***
Loading text1, ..., text9 and sent1, ..., sent9
Type the name of the text or sentence to view it.
Type: 'texts()' or 'sents()' to list the materials.
text1: Moby Dick by Herman Melville 1851
text2: Sense and Sensibility by Jane Austen 1811
text3: The Book of Genesis
text4: …

我正在为我正在进行的项目执行CSV导入工具.客户端需要能够在excel中输入数据,将它们导出为CSV并将它们上传到数据库.例如,我有这个CSV记录:

   1,   John Doe,     ACME Comapny   (the typo is on purpose)

当然,这些公司被保存在一个单独的表中并与外键相关联,因此我需要在插入之前发现正确的公司ID.我计划通过将数据库中的公司名称与CSV中的公司名称进行比较来实现此目的.如果字符串完全相同,则比较应返回0,并返回一些随着字符串变得更大而变大的值,但是strcmp不会在此处删除它,因为:

"Acme公司"和"Acme Comapny"应该有一个非常小的差异指数,但"Acme公司"和"Cmea Mpnyaco"应该有一个非常大的差异指数或"Acme公司"和"Acme Comp.".即使字符数不同,也应该有一个小的差异索引.此外,"Acme Company"和"Company Acme"应返回0.

因此,如果客户端在输入数据时输入类型,我可以提示他选择他最想插入的名称.

是否有一个已知的算法来做到这一点,或者我们可以发明一个:)？

我有两个字幕文件.我需要一个函数来告诉它们是代表相同的文本还是相似的文本

有时只有一个文件中有"风正在吹......音乐在播放"的评论.但80%的内容都是一样的.该函数必须返回TRUE(文件代表相同的文本).有时会出现像1而不是l(1 - L)这样的拼写错误: 她只能放行李.当然,这意味着函数必须返回TRUE.

我的评论:
该函数应返回文本相似度的百分比 - 同意

"所有人都很开心"和"所有人都不开心" - 这里被认为是拼写错误,因此被视为同一文本.确切地说,函数返回的百分比将更低,但足够高以表示短语是相似的

请考虑是否要在整个文件或搜索字符串上应用Levenshtein - 不确定Levenshtein,但算法必须作为一个整体应用于文件.不过,这将是一个很长的字符串.

例如,我们使用gensim以下方法训练word2vec模型:

from gensim import corpora, models, similarities
from gensim.models.word2vec import Word2Vec

documents = ["Human machine interface for lab abc computer applications",
              "A survey of user opinion of computer system response time",
              "The EPS user interface management system",
              "System and human system engineering testing of EPS",
              "Relation of user perceived response time to error measurement",
              "The generation of random binary unordered trees",
              "The intersection graph of paths in trees",
              "Graph minors IV Widths of trees and well quasi ordering", …

我正在尝试使用TF-IDF将文档分类.我已经为某些文档计算了tf_idf,但是现在当我尝试计算其中两个文档之间的余弦相似度时,我得到一个追溯说:

#len(u)==201, len(v)==246

cosine_distance(u, v)
ValueError: objects are not aligned

#this works though:
cosine_distance(u[:200], v[:200])
>> 0.52230249969265641

切片向量使len(u)== len(v)正确的方法？我认为余弦相似性适用于不同长度的矢量.

我正在使用这个功能:

def cosine_distance(u, v):
    """
    Returns the cosine of the angle between vectors v and u. This is equal to
    u.v / |u||v|.
    """
    return numpy.dot(u, v) / (math.sqrt(numpy.dot(u, u)) * math.sqrt(numpy.dot(v, v))) 

另外 - 向量中tf_idf值的顺序是否重要？它们应该被分类 - 或者对于这个计算是否不重要？

这是一个数学问题而不是其他任何问题.假设我在Python中有两个不同大小的列表

listA = ["Alice", "Bob", "Joe"]
listB = ["Joe", "Bob", "Alice", "Ken"]

我想知道这两个列表有多少重叠百分比.订单在列表中并不重要.找到重叠是很容易的,我已经看过其他关于如何做到的帖子,但我无法在脑海中扩展它以找出它们重叠的百分比.如果我按照不同的顺序比较列表,结果会有不同的结果吗？这样做的最佳方式是什么？