col*_*ang 9 c# algorithm search pattern-matching decision-tree
对于一个简单的数组长度为5的问题(实际上数组长度可能是20 ..)
我有一个预定义的一套模式,如AAAAB,AAABA,BAABC,BCAAA,....每个模式与输入数组的长度相同.我需要一个函数,它接受任何整数数组作为输入,并返回它匹配的所有模式.(一个数组可能匹配几个模式)尽可能快.
" A "表示在该模式中,A位置的所有数字都相等.例如,AAAAA仅表示所有数字相等,{ 1,1,1,1,1 }与AAAAA匹配.
" B "表示位置B处的数字不等于A位置处的数字.(即,不是A的数字的通配符)B表示的数字不必相等.例如,ABBAA表示第1,第4,第5个数字等于,例如x,第2个,第3个不等于x. { 2,3,4,2,2 }与ABBAA相匹配.
" C "表示该位置可以是任何数字(即数字的通配符).{ 1,2,3,5,1 }匹配ACBBA, { 1,1,3,5,1 }也匹配ACBBA
我正在寻找一种有效的(在比较数字方面)算法.它不一定是最优的,但不应该是最佳的.我觉得它有点像决策树......
尝试将每个模式与输入匹配.说AABCA反对{a,b,c,d,e}.它检查是否(a=b=e && a!=c).
如果模式的数量是n,模式/数组的长度是m,则复杂度约为O(n*m)
请随意为这个问题提出更好的措辞,因为我不知道如何在没有混淆的情况下简单地理解问题.
理想的算法需要某种准备,比如将模式集转换为决策树.因此,对于某些特殊模式集,预处理后的复杂性可以实现为O(log n*log m).(只是猜测)
一些可能有用的数字:预定义的模式集大约为30个.要匹配的输入数组的数量大约为1000万.
比如说,如果AAAAA和AAAAC都在预定义的模式集中.然后,如果AAAAA匹配,AAAAC也匹配.我正在寻找一种可以识别的算法.
@Gareth Rees的回答给出了一个O(n)解决方案,但假设没有很多" C ".(否则存储量巨大且需要进行许多不必要的比较)
我也欢迎任何有关如何处理存在许多" C "的情况的想法,例如,对于长度为20的输入数组,每个预定义模式至少有10个" C ".
这是一个为O(n)-ish运行时交换O(2 n)准备和存储的想法.如果您的阵列不超过机器的字大小(您暗示20是典型大小),或者如果模式中没有太多的C出现,这个想法可能适合您.(如果这些条件都不满足,请避免!)
(准备步骤,完成一次.)创建字典d将数字映射到模式集.对于每个模式p,并且每个子集小号的出现的Ç在该模式,让Ñ是具有对应的一组比特到每个数阿在的模式,以及用于每次出现Ç在小号.将p添加到模式组d [ n ].
(剩余的步骤每一个新的阵列需要对图案进行匹配时完成的.)创建字典ë映射个数为数字.
让j遍历数组的索引,并为每个j:
设I是数组中的第j个整数.
如果我不在字典e中,则设置e [ i ] = 0.
设e [ i ] = e [ i ] + 2 l - j - 1其中ℓ是数组的长度.
现在e的键是数组中的不同数字i,并且值e [ i ]具有对应于数组中每次出现的i的设置位.对于在字典d中找到的每个值e [ i ],集合d [ e [ i ]]中的所有模式都与阵列匹配.
(注意:在实践中,你会反过来建立位集,并在步骤3.3 使用2 j而不是2 l - j - 1,但为了清晰起见,我已经用这种方式描述了算法.)
这是一个例子.假设我们有AABBA和ACBBA模式.在预处理步骤中,AABBA变为数字25(二进制11001),ACBBA变为数字25(二进制11001)和17(二进制10001),模式中出现C的两个可能子集.字典d看起来像这样:
在处理阵列{1,2,3,5,1}之后,我们得到e = {1→17,2→8,3→4,5→2}.在d中找到值e [1] = 17 ,因此该输入与模式ACBBA匹配.
在处理阵列{1,1,2,3,1}之后,我们得到e = {1→25,2→4,3→2}.在d中找到值e [1] = 25 ,因此该输入与模式AABBA和ACBBA匹配.