感谢那些尝试挑战 7 的人。 希望即使您没有机会，您也一直在关注讨论。 我们如何解决这个挑战？ 从概念上讲，最简单的方法是找到单个字符重复项，然后是两个字符重复项、三个字符重复项，以此类推，增加一个字符，直到没有重复项为止。 天真地检查给定长度的所有可能字符串随着子字符串长度的增加而变得越来越耗时。 对于长度约为 30K 个字符的 Covid-19 基因组，即使我们保证有七个字符的子字符串重复项，但只有 4 个7 = 16,384 种独特组合，仅出现 6889 种 (42%)。 随着子字符串变长，可能重复的数量迅速增加，重复的数量会减少。 必须找到一种有效的方法来识别重复项，才能使这种方法起作用。 在我们研究了解决这个问题的其他方法之后，我们将回到这个问题。
让我们专注于找到最长的重复项，而不必担心找到所有重复项。 一个简单的方法是在第一个字符处开始子字符串，其中包含七个字符的重复项，因为必须存在一个。 然后，一次增加一个字符，直到没有重复。 移动到下一个字符和更长的重复子字符串。 继续此操作，直到您足够接近搜索字符串的末尾，以至于不可能出现重复。 在 Covid-19 基因组中，一个八字符的子串阿塔阿格可以从第一个字符开始构建。 移动到第二个字符，一个 11 个字符的字符串TTAAAGGTTTA盯着位置 2 在位置 20063 有一个副本。 从位置 3 开始没有重复的 11 个字符或更长的字符，因此我们移动到位置 4。 等等。 下面的代码需要大约 5 秒来找到最长的重复字符串，两个 32 个字符重叠的字符串A秒。 请注意，在下面的代码中，当与已找到的最长子字符串长度相等的子字符串存在重复项时，尽管在终止之前至少迭代一次。 在这些情况下下一个长度需要减1。
findLongestDupe = Function({inString,charSet},{parts,nextLen,nextPos=1,longestDupes={""}},
parts = Items(inString,"");
nextLen = Floor(Log(Length(inString))/Log(N Items(charSet)));
While(nextPos <= Length(inString)-nextLen+1,
nextWord = Concat Items(parts[nextPos::(nextPos+nextLen-1)],"");
While(Contains(inString,nextWord,nextPos+1),
nextLen++;
nextWord = Concat Items(parts[nextPos::(nextPos+nextLen-1)],"");
);
nextPos++;
If(Length(nextWord)>Length(longestDupes[1]),
nextLen--; //nextLen will be one more than longest length when Pat Match fails
nextWord = Concat Items(parts[nextPos::(nextPos+nextLen-1)],"");
If(Length(nextWord)==Length(longestDupes[1])+1,
Insert Into(longestDupes,nextWord),
longestDupes = Eval List({nextWord})
);
);
nextChar++;
);
longestDupes;
);
与@Craige_Hales ' 上一篇博文中发布的代码，我尝试使用模式匹配实现上述方法。 令人惊讶的是，结果花费了五到六倍的时间。 我不确定为什么，但我的直觉是（如上次所示）包含当子字符串重复出现的频率较低时，速度要快得多。
我们可以利用 JMP 的内置重复查找器来加快速度，即概括桌台。 这种方法的一个优点是我们可以从任何子串长度开始。 你应该如何构建子字符串？ 在上个月的博文中可以找到两种解决方案。 第一个原子化并迭代输入字符串。
parts = Items(inString,"");
nInds = Length(inString) - subStringLen + 1;
stringList = {};
For(i=1,i<=nInds,i++,
Insert Into(stringList,Concat Items(parts[i::(i + subStringLen - 1)],""))
);
在哪里字符串是输入字符串并且子字符串长度是正在构建的子字符串的长度。 可以使用表达式实现非迭代方法：
parts = Items(inString,"");
nInds = Length(inString) - subStringLen + 1;
stringList = {};
i=1;
stringList[1::nInds] = Expr(Concat Items(parts[i::(i++ + subStringLen - 1)],""));
stringList = Eval List(stringList);
或模式匹配
stringList = {};
Pat Match(inString, Pat Len(subStringLen) >> nextWord+Pat Test(Insert Into(stringList,nextWord);0));
为了测试每种方法的速度，我在由四个随机生成的字符组成的 1,000,000 个字符长的输入字符串上构建了大小为 4、9、15 和 21 的子字符串。 每个长度运行十次迭代。 下面的结果显示了模式匹配的优越性。 完整的结果可以在测试构建子字符串.JMP .
算法
|
字符串长度构造时间（秒）
|
4个
|
9
|
15
|
21
|
表达式
|
6.91
|
7.35
|
8.19
|
9.01
|
环形
|
2.56
|
2.98
|
3.62
|
4.26
|
模式匹配
|
1.09
|
1.12
|
1.10
|
1.11
|
执行方差分析显示算法、字符串长度和算法 x 字符串长度交互的统计差异 (p << 0.001)。 使用 Tukey 的 HSD 进行的事后测试表明，模式匹配算法的字符串长度级别之间没有统计差异。 为了解此方法如何处理更大的字符集，我们使用随机选择的 26 个字符构建的 1,000,000 个字符长的字符串进行了测试。 在与上述相同的子字符串长度加上 2 个和 40 个字符的子字符串上运行 20 次重复。 虽然存在统计差异，但实际差异很小。
子串
长度
|
时间（秒）
|
2个
|
1.11
|
4个
|
1.08
|
9
|
1.09
|
15
|
1.11
|
24
|
1.13
|
40
|
1.53
|
将子字符串构造和重复查找放在一起可能类似于下面的代码。 了解与重复项关联的行后，我们就可以确定它们在字符串中的位置。 这将在稍后对我们有利。 将表设为私有可以略微加快操作速度。
stringList = {};
Pat Match(inString, Pat Len(subStringLen) >> nextWord+Pat Test(Insert Into(stringList,nextWord);0));
tmpTbl = New Table("tmp",New Column("tmp",Character,Values(stringList)),Private);
sumTbl = tmpTbl << Summary(Group(:tmp),Private);
dupeLocs = sumTbl << Get Rows Where(:N Rows > 1);
dupes = Column(sumTbl,1)[dupeLocs];
Close(tmpTbl,No Save);
下表给出了基于使用 Covid-19 和 1,000,000 个字符串运行 10 次的单次迭代的平均运行时间。 鉴于结果，很容易看出，随着字符串和子字符串变大，只使用这种方法且不进行子字符串大小优化会出现问题。
子串
长度
|
新冠肺炎
|
1M
|
2个
|
0.0517
|
1.68
|
4个
|
0.0504
|
4.25
|
9
|
0.1837
|
8.29
|
15
|
0.2226
|
8.63
|
21
|
0.2209
|
8.85
|
40
|
0.2957
|
12.30
|
即使开始子字符串大小优化，我们也无法预测输入数据的结构有多少。 更好的方法是采用混合策略。 使用概括识别给定大小的重复项，然后单独使用这些重复项，找到可以从中构建的最长重复项。 这将起作用，因为最长重复项的子字符串必须出现在从较短子字符串长度创建的重复项集中。 有几种可能的方法。 我选择了一种类似于但不同于要讨论的最终方法的方法。 老实说，在提出这种方法之前，我看到了最终的方法，毫无疑问，我深受其影响。 我选择的方法的挑战是创建一个数据结构来跟踪原始子字符串的位置。 代码出奇地短，大约 50 行，间距很大。 找到 Covid-19 数据中的所有重复项大约需要 0.32 秒，找到 1,000,000 个字符的字符串需要 13 秒。 代码可以在findLongestDupe（摘要）.JSL .
概括用于在每次迭代中查找重复项。 虽然这对于大表来说很慢，但我们只需要构建与上一步中的重复项一样大的表。 从子串长度开始，超过最小长度一个字符以保证重复，重复的总数可能会减少，如果不是立即的话，那么会很快。 如果几次迭代中的行数不太大，则可以使用此方法而无需进一步优化，例如从较长的子字符串开始。 这种方法的一个优点是可以在这些情况下使用额外的优化。 用于跟踪初始字符串位置的索引以可能与关联数组一起使用的方式工作，这就是要讨论的最终方法中使用的内容。 首先找到具有初始长度的重复字符串的位置并将它们保存到一个临时数组中。 从这些位置开始构建长一个字符的字符串，确保删除任何超出输入字符串边界的字符串。 在此列表中查找重复字符串的位置。 我们可以将这些新索引链接回原始位置，方法是将它们用作先前保存的数组的索引，只保留那些具有索引的元素。 用这个替换之前的数组。 继续，直到没有重复项为止，此时前一个数组包含最长重复项的位置。
如上所述，最终方法在风格上与前一种相似。 这种方法的想法是由于@brady_brady . 有一些重要的区别。 首先，它从一个字符开始构建所有子串。 虽然这听起来效率低下，但通过使用关联数组并使用矩阵为各个字符串字符编制索引，它消除了直接搜索字符串并避免了不存在的字符组合。 总的来说，当字符集和输入字符串变大时，它优于以前的方法。 对各种输入字符串大小 (50K – 2.5M) 和字符集（4 至 72）进行了十次运行，以比较这两种方法。 摘要方法 (1) 和关联数组方法 (2) 的平均运行时间如下所示。 完整的结果可以在 Compare fastest methods.JMP 中找到。
|
50K
|
100K
|
500K
|
1M
|
2.5M
|
字符集大小
|
1个
|
2个
|
1个
|
2个
|
1个
|
2个
|
1个
|
2个
|
1个
|
2个
|
4个
|
0.5087
|
0.5814
|
0.9081
|
1.2664
|
5.421
|
6.813
|
13.412
|
13.778
|
32.23
|
35.67
|
10
|
0.2724
|
0.4117
|
0.6251
|
0.9207
|
2.850
|
4.509
|
6.998
|
9.503
|
13.61
|
24.70
|
26
|
0.3098
|
0.3748
|
0.6786
|
0.7441
|
3.625
|
3.981
|
7.363
|
8.537
|
21.68
|
19.58
|
52
|
0.4247
|
0.3265
|
1.0617
|
0.7682
|
4.246
|
4.046
|
9.522
|
7.395
|
30.67
|
18.08
|
72
|
0.3186
|
0.3309
|
0.7308
|
0.7079
|
3.533
|
4.236
|
7.192
|
8.917
|
20.14
|
18.97
|
与 Summary 方法一样，此方法首先将输入字符串转换为单个字符。 然而，不是直接使用字符，而是使用它们在字符集中出现的数字位置。 这允许使用矩阵运算来构建子串，这往往比字符串运算更快。 具体来说，第一次迭代将每个字符集位置的矩阵表示作为关联数组的键（例如，[3] 表示 G），并使用其在输入字符串中的位置向量作为其值。 每个后续迭代都从构建一个新的关联数组开始，方法是找到 1 处的输入字符串值加上前一个数组中每个键的向量值，注意不要超出输入字符串中的最后一个元素。 与递增矢量的第一个元素对应的值用于搜索其余递增矢量值以查找重复项。 如果它们存在，则将它们关联的位置用作新数组元素中的值。 该元素的键是通过将重复元素的字符集值连接到原始键来构建的，从而可以轻松地重新创建字符串。 搜索值及其重复项（如果存在）将从向量中删除并继续搜索，直到没有值为止。 此构建过程针对前一个数组中的每个元素进行。 完成后，新的关联数组将替换旧的，并开始下一次迭代。 这一直持续到没有新的键来替换以前的数组。 前一个数组包含最长的重复项。
Brady 的代码可以在findLongestDupe (AA).JSL . 我做了一个小调整以允许使用不同的字符集。
下一次我们将从字符串转移到列表。 正如在之前的博客中提到的，避免迭代一直是最近两篇社区帖子的主题，涉及将数字元素转换为字符和列表索引. 下次有两个挑战。 它们基于链接帖子中出现的问题。 在这两种情况下。 您正在将数值转换为字符串。
- 编写一个函数来转换列表n列表（每个都有米我数）。 不要假设米我对于所有列表都是一样的。
- 编写一个可以从第 1 项转置列表的函数。 这是一个小例子：
inputList = {{12, 11, 16, 1, 15, ., 23, 8, 16, 17}, {1, 10, ., 4, 25, ., 19, 21, ., 3}, {11, 21,
22, 7, 3, ., 24, 10, 21, 20}, {., ., ., ., ., ., ., ., ., .}, {11, ., 3, ., 9, ., 23,
., 3, 16}};
outputList = {{12, 1, 11, ., 11}, {11, 10, 21, ., .}, {16, ., 22, ., 3}, {1, 4, 7, ., .}, {15, 25,
3, ., 9}, {., ., ., ., .}, {23, 19, 24, ., 23}, {8, 21, 10, ., .}, {16, ., 21, ., 3},
{17, 3, 20, ., 16}}
祝你好运！
这是应对挑战的一种方法。 我决定“不要假设米所有列表都相同”意味着可能需要用缺失值填充跨列表。 Repeat({.},10) 生成 {.,.,.,.,.,.,.,.,.,.}。 Insert() 添加列表中的项目，而不是列表（参见如何将一个列表插入另一个列表.)
inputList = {
{12, 11, 16, 1, 15, ., 23, 8, 16, 17},
{1, 10, ., 4, 25, ., 19, 21, ., 3},
{11, 21, 22, 7, 3, ., 24, 10, 21, 20},
{1}, // odd across-list
{., ., ., ., ., ., ., ., ., .},
{11, ., 3, ., 9, ., 23, ., 3, 16}};
// find rows and max cols of input:
nrows = N Items( inputList );
ncols = 0;
For( irow = 1, irow <= nrows, irow += 1,
ncols = Max( ncols, N Items( inputList[irow] ) )
);
// if the across-lists are not all the same size, add missing values
For( irow = 1, irow <= nrows, irow += 1,
If( ncols > N Items( inputList[irow] ),
Insert Into( inputList[irow], Repeat( {.}, ncols - N Items( inputList[irow] ), . ) )
)
);
// make a table of numbers from the lists
dt = New Table( "temp", invisible, Add Rows( nrows ), <<ADD multiple="" columns=""></ADD>此 JSL 创建一个全缺失数据表，其中包含足够多的行和数值列来保存列表中的数值。 数据表下标对不均匀长度的行不满意，不满意在分配过程中将数字转换为字符。 通过将 SetDataType 消息发送到列列表（避免显式 JSL 循环），转换在接近尾声时完成。转置后的数字列表在此之前捕获。
当列都是数字时，数据表下标希望通过数字矩阵获取和设置，但很乐意从数字列表的列表中设置。 由于 get 将返回一个矩阵，但问题要求是返回一个转置后的数字列表，因此 AsList() 完成了将矩阵（从数据表）转换回列表的工作。
