This topic has been archived. It cannot be replied.
-
工作学习 / 专业技术讨论 / 一个实际项目的算法问题:关于模式匹配.需要支持的通配符:
*: 0~多个字符
-:1个字符
需求:
输入: 多(几千个)PATTERN字串 ARRAY OF PATTERN, 和一个需要MATCH的字串 STR_A
输出: ARRAY OF PATTERN 中,所有和STR_A MATCH 的PATTERN.
如:
输入: ARRAY OF PATTERN 为( A*, -BB, *B, DB-)
STR_A 为 ABB
输出: ( A*, -BB, *B )
需要设计一个最小数量级的算法.
-wanttoknow(bangbang);
2006-3-9
{318}
(#2829461@0)
-
*,- 在字符的左右分别是什么意思？还是搂主的笔误？这一点需要解释清楚，比如 A*A 和 *A-B- 到底该怎么理解？
-binghongcha76(一只大猫);
2006-3-9
(#2829568@0)
-
*代表0到多个字符, -代表一个字符.A*A 代表所有A开头并且A结束的字串.
*A-B-代表所有倒数第四个字符为A并且倒数第二个字符为B的字串.
-wanttoknow(bangbang);
2006-3-9
{93}
(#2829627@0)
-
在简单一点，比如 A-B*C-D，按照左右不同有2种解释：1-〉(A-)(B*)(C-)D , 2-> A(-B)(*C)(-D)... 这2种Patten所匹配的是完全不同的字符串
-binghongcha76(一只大猫);
2006-3-9
(#2829626@0)
-
啊，我明白了，呵呵，我理解成必须和前一个字母有关，sorry 啊
-binghongcha76(一只大猫);
2006-3-9
(#2829636@0)
-
pattern= "A*A"能匹配string "A" 么？
-canadiantire(轮胎-M.I.N.K.);
2006-3-9
(#2829657@0)
-
不行,但可以匹配AA
-wanttoknow(bangbang);
2006-3-9
(#2829660@0)
-
写个NFA就可以了吧？应该不麻烦的。
-canadiantire(轮胎-M.I.N.K.);
2006-3-9
(#2829705@0)
-
在网上找到某人用DFA来解决这个问题的测试结果, 他有40个带通配符(*)的PATTERN, 结果生成了大约130,000个状态, 把1.5G内存全用光了. 而我的应用里有几千个这种PATTERN.在网上找到某人用DFA来解决这个问题的测试结果, 他有40个带通配符(*)的PATTERN, 结果生成了大约130,000个状态, 把1.5G内存全用光了. 而我的应用里有几千个这种PATTERN.
但是他MATCH的是PATTERN, 我要MATCH的是整个字符串, 这一点不同, 不知道是不是可以也用DFA, 但不用这么繁复.
-wanttoknow(bangbang);
2006-3-9
{260}
(#2830177@0)
-
什么是 NFA?
-binghongcha76(一只大猫);
2006-3-9
(#2829743@0)
-
你没系统学过计算机课吧？
-canadiantire(轮胎-M.I.N.K.);
2006-3-9
(#2829763@0)
-
不满您说，我就没学过计算机，我大学专业是物理，只是对逻辑挺感兴趣
-binghongcha76(一只大猫);
2006-3-9
(#2829787@0)
-
不知道是否准确: NFA是不确定有限自动机, DFA是确定有限自动机.
-wanttoknow(bangbang);
2006-3-9
(#2830179@0)
-
算法关键:1)将patten 串中的 * 转换成与MARTH字串 STR_A等长的单字通配符号(例如#);
2) 将MARTH字串 STR_A滑过patten 串比较即可;
如:
输入: ARRAY OF PATTERN 为( A*, -BB, *B, DB-)
转化为: A###,-BB,###B,DB-)
STR_A 为 ABB
中间输出: A##, ###, -BB, ###,##B)
反转换 :##..----> *;
A*,*,-BB,*,*B; 再扔掉 单个*; 得最后
输出: ( A*, -BB, *B )
需要设计一个最小数量级的算法.
-eagle_no1(瞎起哄);
2006-3-9
{369}
(#2829761@0)
-
'*' 表示0到多个字符串, 请问怎么匹配 *CD* 跟 'ACDWFGAB'
-wanttoknow(bangbang);
2006-3-9
(#2830193@0)
-
########CD########匹配ACDWFGAB; 得匹配窜#CD#####; 转换为*CD*;
-eagle_no1(瞎起哄);
2006-3-10
(#2831780@0)
-
''*' 表示0到多个字符串' 的意思是说字符串的长度事先是不知道的, 所以不可能预先知道把它换成多少个 '#' 号.
-wanttoknow(bangbang);
2006-3-11
(#2833247@0)
-
匹配时动态转;
-eagle_no1(瞎起哄);
2006-3-11
(#2833274@0)
-
怎么动态转法?
-wanttoknow(bangbang);
2006-3-11
(#2833445@0)
-
回头看看你们的算法,总觉得把简单的事情搞复杂了; 动态转是这样的如和 'ACDWFGAB' 匹配,将*转成8个#; 和"abc"匹陪时将*转成3个#;
当然这只是算法描述; 实现时可做优化
-eagle_no1(瞎起哄);
2006-3-11
{99}
(#2833465@0)
-
我的建议input: str as string, pattern as string
扫描string, 同时取下一个pattern，
如果pattern_char == '*' 取下一个pattern_char
如果pattern 不等于*/-, 则string_char 必须等于pattern_char, 不等于就是不匹配；
如果last_pattern_char等于*,则滑过若干string_char直到pattern_char ==string_char,
如果pattern_char等于-, 责任字符都匹配，
loop.
-canadiantire(轮胎-M.I.N.K.);
2006-3-9
{339}
(#2829786@0)
-
你这好象是逐个PATTERN进行比较吧?这是最慢的算法, 不到万不得已不会用的. 我有几千个PATTERN, 这种做法会太慢了.
-wanttoknow(bangbang);
2006-3-9
(#2830202@0)
-
还不至于是最慢的算法吧？O(n)的算法了，莫非你能搞出更快的？
-canadiantire(轮胎-M.I.N.K.);
2006-3-9
(#2830242@0)
-
假设每个PATTERN和测试字符串的长度都为n. 在只用一个PATTERN的情况下, 考虑到MATCH '*' 需要回溯, 其算法时间是 O(n^2).
有k个PATTERN, 其时间就是 O(k*n^2)了.
-wanttoknow(bangbang);
2006-3-9
(#2830256@0)
-
恩，你讲得有道理，我开始的确没有仔细考虑这个问题。
-canadiantire(轮胎-M.I.N.K.);
2006-3-9
(#2830406@0)
-
兄弟，你的算法有错误，最后一行
-binghongcha76(一只大猫);
2006-3-9
(#2830316@0)
-
如果每个PATTERN没有什么联系，或者联系少，即使你作什么PRE-PROCESS，也不能确定能减少COMPLEXITY，除了逐个比较，还能怎么样？很多语言都支持RE，几千个不算什么。
-yuanzidan(原子弹);
2006-3-9
(#2830224@0)
-
这些PATTERN有相似的可能性很大. 特别是前缀, 或者后缀.
-wanttoknow(bangbang);
2006-3-9
(#2830246@0)
-
可能性很大也只是可能，极端的情况就是毫不相干，有可能PRE-PROCESS的时间和逐一比较的有一拼。实际你是在问PRE-PROCESS的算法
-yuanzidan(原子弹);
2006-3-9
(#2830295@0)
-
就让我们当这些PATTERN有很多相同的前缀吧. 除了逐一比较, 还有什么方法?
-wanttoknow(bangbang);
2006-3-9
(#2830310@0)
-
难，不确定因素太多，相同也是比过才知道的吧，*也算相同吧，实际上你是把以后的逐一比较的COMPLEXITY放在了PRE-PROCESS里了，具体你省了多少很难估算。
-yuanzidan(原子弹);
2006-3-9
(#2830420@0)
-
搂主，你那几千数组是什么意思？是pattern数组的长度是几千还是pattern里面每一个unit的长度是几千？ 如果追求速度可以把我的程序改在C++下运行会比在.net下运行快一些，不知能否满足你的要求？
-binghongcha76(一只大猫);
2006-3-9
(#2830473@0)
-
各位老大，你们那些算法我怎么都看不懂呀！没有人实际编程是一下吗？
-binghongcha76(一只大猫);
2006-3-9
(#2830338@0)
-
这儿都是10万年薪以上的Architect，没人亲自写code
-eglington(eglington);
2006-3-9
(#2830414@0)
-
我来给出程序，C#版，递归算法。欢迎大家测试，有错误及时通知我！别说，这题比前几天的排列组合是难一些
-binghongcha76(一只大猫);
2006-3-9
{4501}
(#2830408@0)
-
感谢rolia网友有情提醒，程序有个小小的bug，但不影响大局，晚上改正
-binghongcha76(一只大猫);
2006-3-10
(#2831050@0)
-
不好意思, 我不懂C#. 请简单介绍一下算法.
-wanttoknow(bangbang);
2006-3-10
(#2831082@0)
-
再澄清一下: PATTERN 有几千个; 每个PATTERN的长度不超过50个字符. TEST字符串的长度也不超过50个字符. 其实, 我自己设计了两个行得通的算法, 但是感觉时间复杂度还是大了.
-wanttoknow(bangbang);
2006-3-10
{584}
(#2831119@0)
-
所以希望有过类似经验的大侠指点则个.
-wanttoknow(bangbang);
2006-3-10
(#2831127@0)
-
先说一下，我也没什么经验。刚才用fgrep测试了一下, 首先用程序生成一个包含5000个随机pattern的文件，每个pattern的长度从25-50不等。然后找了一段5K的文本，用fgrep match了一下，连一秒钟都没用。
-canadiantire(轮胎-M.I.N.K.);
2006-3-10
(#2831255@0)
-
嗯，这个有问题，fgrep好像不对。grep 慢得多了。
-canadiantire(轮胎-M.I.N.K.);
2006-3-10
(#2831276@0)
-
您的PATTERN都包含通配符了吗? 另外, 我只需要EXACT MATCH, 即用来匹配的'文本' 跟某一个或某几个PATTERN正好匹配, 而不是只包含这些PATTERN.
-wanttoknow(bangbang);
2006-3-10
(#2831563@0)
-
那个结果并不正确,我也是被answers.com忽悠了。但是用grep花的时间也是不很长，大概5分钟左右。
-canadiantire(轮胎-M.I.N.K.);
2006-3-10
{1000}
(#2831743@0)
-
5分钟实在太太太长了. 不过, 你试试用50BYTE的文本, 而不是5k的文本, 可能不会这么吓人. 另外, 您的IDEA, 不是很好懂, 能否更具体点. :)
-wanttoknow(bangbang);
2006-3-10
(#2832002@0)
-
看一下这个图可能说得清楚些
-canadiantire(轮胎-M.I.N.K.);
2006-3-10
(#2832883@0)
-
进不去看这个图, 出错信息: 403 Forbidden:
You don't have permission to access /uploads/67cd1648e2.png on this server.
-wanttoknow(bangbang);
2006-3-11
(#2833109@0)
-
搂主，我的程序5000次匹配测试用了不到1秒钟（640毫秒），这还是用效率最低的string来做，改成byte优化后会更快，我不知你要快到什么地步？我的测试字符串
string array = "1234567890123456789012345678901234567890"; // 40个字符
string[] pattern = { "*123456789-*", "1234567890----------1234567890----*", "----------1234567890------*--1234567890", "----------1234*--234567890-" };
这是4个测试pattern, 我把它简单的*1250,最后实际的pattern数组长度是5000，我想这样能大概反映出平均运算速度。
实际运算时间640毫秒，AMD Athlon XP 2200+, 1G RAM
现在太忙，晚上回家我简单写一下算法
-binghongcha76(一只大猫);
2006-3-10
{450}
(#2831281@0)
-
有趣，发现grep德pattern个数和搜索事件不是线性关系。1000各pattern飞快，2000个就开始慢得难受了。
-canadiantire(轮胎-M.I.N.K.);
2006-3-10
(#2831302@0)
-
这个，sorry 啊，grep是什么软件？我从没听说过
-binghongcha76(一只大猫);
2006-3-10
(#2831316@0)
-
grep
-canadiantire(轮胎-M.I.N.K.);
2006-3-10
(#2831394@0)
-
数据结构学过一个匹配算法，不过基本忘了。我觉得它的原理可以用在这里：逐字比较string和所有pattern, 不回头。设一个大数组存每个patten的状态。一遍就完。
-holdon(again);
2006-3-10
(#2831823@0)
-
不知是否Karp-Rabin算法？
-wllee(Lottolee);
2006-3-24
(#2863293@0)
-
你是要完全匹配？string AAA 匹不匹配 模式A-? 如果不，那可以先处理这几千个模式，他们肯定有矛盾的, 匹配A-就就不可能匹配B-
-holdon(again);
2006-3-10
(#2831897@0)
-
有道理, 让我想想...
-wanttoknow(bangbang);
2006-3-10
(#2831982@0)
-
关键还是看这些patten什么样。我觉得可以先按长度建个数组1~50, 每个数组里放可能的模式。有*就放到最小长度~50,再在每个数组里找一种算法（简单的就按第一个字符分，肯定有什么复杂的更好的算法）细分到二极数组, 这样如果模式比较均匀的话（最好不要太多*) 可能只需要比较 原来模式的1/100。
-holdon(again);
2006-3-10
{167}
(#2832722@0)
-
各位, 我找到这篇文章, 似乎可以解决这个问题, 其算法时间复杂度是 O((|t|+|P|)*log|P|)
http://citeseer.ist.psu.edu/cachedpage/132839/1
一时半刻还没看懂, 有兴趣的可以一起分析分析.
-wanttoknow(bangbang);
2006-3-11
(#2833241@0)
-
我的测试结果: 进行1百万次匹配(2000个Pattern，来匹配500个字符串)，费时五秒。
-hunterz(Hunter);
2006-3-13
{2298}
(#2836687@0)
