搜索列表是否有相应的StringPosition []？如果没有,实现这个的最快方法是什么？

Question

是否有一个函数可以搜索元素序列中的子序列？我找了一个模拟StringPosition的List秒.在我目前的应用程序,我用整数名单的工作,但我很想在一般FindSequence[list, pattern, n]功能,将找到的第一个n的出现pattern在list.

---

这是一个玩具示例:

生成一些数据:

In[1]:= $HistoryLength = 0    
Out[1]= 0

In[2]:= Timing[digits = First[RealDigits[\[Pi], 2, 10000000]];]    
Out[2]= {26.5, Null}

让我们将它转​​换为字符串,以便我们可以比较StringPosition.这是一个非常缓慢的记忆饥饿.(评估完成后,内存将被释放.)

In[3]:= Timing[str = StringJoin[ToString /@ digits];]    
Out[3]= {43.813, Null}

我正在寻找这个子序列:

In[4]:= patt = {1, 1, 1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 1, 0, 
   1, 0, 1, 1};

In[5]:= strpatt = StringJoin[ToString /@ patt];

搜索字符串非常快:

In[6]:= StringPosition[str, strpatt] // Timing    
Out[6]= {1.047, {{5737922, 5737943}}}

这是搜索数值数组的简单实现.它比StringPosition以下慢:

In[7]:= Timing[
           corr = ListCorrelate[patt, digits];
           Select[Flatten@Position[corr, patt.patt], 
             digits[[# ;; # + Length[patt] - 1]] === patt &]
        ]

Out[7]= {2.234, {5737922}}

---

摘要:

1. 是否有内置搜索列表的子序列？
2. 如果没有,那么数字列表的快速优雅实现是什么(我的实际问题)？
3. 那些可以包含任何内容的通用列表呢？(这里有两种可能性:只有"静态"模式{1,0,1},或者类似的一般模式{1,_,1},尽管后面这些模式可能会带来复杂性.)

我希望这会有很多解决方案,有些快,有些更优雅,有些更通用:-)

---

相关问题:

• 在Mathematica中快速实现Position2D(2D情况相同)
• 在Mathematica中找到(重复)列表的周期的最佳方法是什么？

有趣的阅​​读:

• Boyer-Moore字符串搜索算法

---

编辑:

我刚发现没有证件LongestCommonSubsequencePositions. LongestCommonSubsequencePositions[a, b]会发现列表中的最长公共子a和b,并返回它的位置,第一只在双方发生a和b.(记录在案的LongestCommonSubsequence,我不知道,只会返回子序列本身,而不是它的位置.)

它比上面的替代方案慢,但它适用于可以包含任何表达式的通用列表.

In[57]:= LongestCommonSubsequencePositions[digits, patt] // Timing
Out[57]= {5.25, {{5737922, 5737943}, {1, 22}}}

Answer 1

您可以使用ReplaceList"前缀"和"后缀" ___并匹配整个列表.这为您提供了可以进行的所有替换(而不是Replace).你的模式的位置就是前缀+ 1的长度.它也很快:

In[40]:= Timing[ReplaceList[digits, Join[{pre___}, patt, {___}] :> Length[{pre}]
   + 1]]

Out[40]= {1.3059, {5737922}}

编辑:认为使用延迟规则比使用后映射更优雅Length.