标签: string-matching

这是"算法设计和分析导论"中的练习.这是一个字符串匹配问题.假设我有字符串ABCD,并且有一个模式XY.并希望查看字符串是否包含模式.

我们假设在这里使用蛮力,所以从左到右的比较是将A与X进行比较,接下来是将B与X进行比较等.而从右到左的比较是将B与Y进行比较,接下来是比较C与B.暗示说从右到左的比较确实有优势,但我不明白为什么.

任何提示都很感激!

可能重复:
Javascript:从字符串中删除非数字字符

字符串匹配对我来说很头疼.

例:

如果我有这样的字符串:

abc123xyz456()*
^%$111u222

然后将其转换为:

123456
111222

我正在寻找一种有效的方法来提取最短的重复子串.例如:

input1 = 'dabcdbcdbcdd'
ouput1 = 'bcd'

input2 = 'cbabababac'
output2 = 'ba'

我将不胜感激与此问题相关的任何答案或信息.

另外,在这篇文章中,人们建议我们可以使用正则表达式

re=^(.*?)\1+$

找到字符串中最小的重复模式.但是这样的表达式在Python中不起作用并且总是返回一个不匹配(我是Python的新手,也许我想念一些东西？).

- - 跟进 - -

这里的标准是寻找最短的非重叠模式,其长度大于1并且具有最长的总长度.

我正在使用大量的产品数据集(约100万).这些产品来自许多不同的来源,因此它们的数据列表不一致.其中一个重大问题是差异产品品牌名称(约17,000个独特品牌).有些品牌需要多达10个差异,需要将它们联系在一起.

问题:

1. Inconsistant Spacing:Jet Boil VS Jetboil
2. 标点符号: Granger的VS格兰杰
3. 噪音词:北脸VS北脸
4. Taxomonies: Armada VS Armada Skis
5. 符号: Phil和Teds VS Phil&Teds
6. 错误拼写: Patagonia VS Pategonia
7. 其他奇观:贝尔体育VS贝尔体育#81037

示例数据集

Black Diamond
Black Diamond (Uda)
Black Diamond Co
Black Diamond Eq Ltd
Black Diamond Eqp #76800
Black Diamond Equipment
Black Dog Machine Llc
Black Dome Press
Black Dot
Black Dragon
Black Fire
Black Flys
Black Forest Girl
Black Gold
Black Hawk Inc.
Black Hills
Black Knight
Black Label
Black Magic …

我想计算文档中特定短语的出现次数.例如"stackoverflow论坛".假设D表示使用包含两个术语的文档设置的文档.

现在,假设我有以下数据结构:

A[numTerms][numMatchedDocuments][numOccurInADocument] 

其中numMatchedDocuments是D的大小,numOccurInADocument是特定术语在特定文档中出现的次数,例如:

A[stackoverflow][document1][occurance1]=3;

意味着,术语"stackoverflow"出现在文档"document1"中,并且它的第一次出现在位置"3".

然后我选择发生最少的术语并遍历其所有位置,以查找"论坛"是否出现在当前术语"stackoverflow"位置+ 1的位置.换句话说,如果我在第4位找到"论坛",那么这是一个短语,我找到了匹配.

每个文档的匹配很简单,并且运行速度相当快,但是当文档数量超过2,000,000时,它变得非常慢.我已经将它分发到核心上,当然它变得更快但是想知道是否有更好的算法.

谢谢,

Psudo码:

boolean docPhrase=true;
int numOfTerms=2;
// 0 for "stackoverflow" and 1 for "forums"
for (int d=0;d<D.size();d++){
 //D is a set containing the matched documents
 int minId=getTheLeastOccuringTerm();
 for (int i=0; i<A[minId][d].length;i++){ // For every position for LeastOccuringTerm
   for( int t=0;t<numOfTerms;t++){ // For every terms
      int id=BinarySearch(A[t][d], A[minId][d][i] - minId + t);
      if (id<0) docPhrase=false;
   }
 }
}

我正在寻找一种高效的算法，能够找到与特定字符串匹配的所有模式。模式集可能非常大（超过100,000个），并且可能是动态的（随时添加或删除的模式）。模式不一定是标准的regexp，它们可以是regexp的子集或类似于shell模式的东西（即：）file-*.txt。最好使用正则表达式子集的解决方案（如下所述）。

仅供参考：我对基于RegExp列表的蛮力方法不感兴趣。

通过简单的正则表达式，我的意思是一个正则表达式支持?，*，+，字符类[a-z]和可能的逻辑运算符|。

为了阐明我的需求：我希望找到所有与URL匹配的模式：

http://site1.com/12345/topic/news/index.html

响应应该是基于以下模式设置的这些模式。

http://*.site1.com/*/topic/*
http://*.site1.com/* 
http://*

模式集：

http://*.site1.com/*/topic/*
http://*.site1.com/*/article/*
http://*.site1.com/* 
http://*.site2.com/topic/*
http://*.site2.com/article/*
http://*.site2.com/* 
http://*

我有一个字符串向量

x<-c('a','b')

我有一个多列的矩阵; 其中包含该字符串向量中的名称.我想得到与他们的名字相匹配的列号/索引.

which(colnames(sample_matrix) == x)

当x不是矢量而是单个元素时,上述情况适用.有解决方案吗

我想存储大量(〜数千)字符串,并能够使用通配符执行匹配.

例如,以下是示例内容:

• Folder1
• Folder1/Folder2
• Folder1/*
• Folder1/Folder2/Folder3
• Folder2/Folder*
• */Folder4
• */Fo*4

(每行也有附加数据,如标签,但匹配仅针对该键)

以下是我想要与数据匹配的示例:

• Folder1
• Folder1/Folder2/Folder3
• Folder3

(*在这里是一个通配符,它​​可以是一个不同的角色)

我天真地考虑将它存储在MySQL表中并使用%通配符与LIKE操作符,但MySQL索引只适用于通配符左侧的字符,在我的情况下它可以在任何地方(即%/Folder3).

所以我正在寻找一种可以在PHP中使用的快速解决方案.我是开放的:它可以是一个单独的服务器,一个使用正则表达式文件的PHP库,...

给定一个字符串,例如'helloyellowellow',解析给定字符串中的所有有效字符串.(例如:[[地狱,你好,黄色],[低,低] ........]

我正在寻找最优化的编写代码的方法.这是我的,但我不确定这是不是最好的方法.

完全披露 - 这是一个面试问题

master = []

#   Dictionary for us to look up words   
def is_word(inputstr):
    #returns True/False


def processstring(fstr,secstr,li):
    if is_word(fstr): 
        li.append(fstr)
    if len(secstr) == 0:
        if len(li) != 0:
            master.append(li)
        return
    processstring(fstr+secstr[0], secstr[1:len(secstr)],li)



def wrapperprocess(inpstr):
    li = []
    if len(inpstr) == 0:
        return
    processstring('',inpstr,li)
    wrapperprocess(inpstr[1:len(inpstr)])


wrapperprocess('helloyellowellow')
print master

我试图将数据框的列中的字符串与另一个数据框的列中的字符串进行匹配,并映射相应的值.两个数据帧的行数不同

df1 = data.frame(name = c("(CKMB)Creatinine Kinase Muscle & Brain", "24 Hours Urine for Sodium", "Antistreptolysin O Titer", "Blood group O", lonic_code = c("27816-8-O", "27816-8-B", "1869-7", "33914-3")
df2 = data.frame(Testcomponents = c("creatinine", "blood", "potassium"))

预期产出

Test Components          lonic_code
creatinine                27816-8-O
 blood                      1869-7
potassium                    NA