感谢那些尝试挑战 7 的人们。 希望即使您没有机会，您也一直在关注讨论。 我们如何解决这个挑战？ 从概念上讲，最简单的方法是查找单个字符重复项，然后查找两个字符重复项、三个字符等，然后增加一个字符，直到没有重复项。 随着子字符串长度的增加，天真地检查给定长度的所有可能字符串会变得越来越耗时。 对于长度约为 30K 个字符的 Covid-19 基因组，即使我们保证有 7 个字符的子字符串重复项，但只有 4 个字符7 = 16,384 个独特组合，仅出现 6889 个 (42%)。 随着子串变长，可能重复的数量迅速增加，重复的数量会减少。 为了使这种方法发挥作用，必须找到一种有效的方法来识别重复项。 在我们研究了解决这个问题的其他方法之后，我们将回到这个问题。
让我们专注于查找最长的重复项，而不必担心查找所有重复项。 一种简单的方法是在第一个字符处使用七个字符的重复字符开始子字符串，因为必须存在一个重复字符。 然后，一次一个字符地增长它，直到没有重复。 移至下一个字符和更长的重复子字符串。 继续此操作，直到足够接近搜索字符串的末尾，不可能出现重复项。 在 Covid-19 基因组中，一个八字符的子串攻击性攻击可以从第一个字符开始构建。 移动到第二个字符，一个 11 个字符的字符串TTAAGGTTTA盯着位置 2，在位置 20063 处有一个重复项。 从位置 3 开始，没有重复的 11 个字符或更长的字符，因此我们移至位置 4。 等等。 下面的代码大约需要 5 秒来找到最长的重复字符串，两个 32 个字符的重叠字符串A s。 请注意，在下面的代码中，当存在与已找到的最长子字符串长度相等的子字符串时，尽管在终止之前至少再迭代一次。 在这些情况下下一个长度需要减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）进行了 10 次运行，以比较这两种方法。 下面显示了汇总方法 (1) 和关联数组方法 (2) 的平均运行时间。 完整的结果可以在比较最快的方法.JMP 中找到。
|
50K
|
10万
|
50万
|
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 方法一样，此方法首先将输入字符串转换为单个字符。 然而，不是直接使用字符，而是使用它们在字符集中出现的数字位置。 这允许使用矩阵运算来构建子字符串，这往往比字符串运算更快。 具体来说，第一次迭代将每个字符集位置的矩阵表示作为关联数组的键（例如，G 的[3]），并使用其在输入字符串中的位置向量作为其值。 每次后续迭代都首先通过查找 1 处的输入字符串值加上前一个数组中每个键的向量值来构建一个新的关联数组，注意不要超出输入字符串中的最后一个元素。 与递增向量的第一个元素相对应的值用于搜索其余递增向量值的重复项。 如果它们存在，则它们关联的位置将用作新数组元素中的值。 该元素的键是通过将重复元素的字符集值连接到原始键来构建的，从而可以轻松地重新创建字符串。 搜索值及其重复项（如果存在）将从向量中删除，并继续搜索，直到没有值留下。 此构建过程针对前一个数组中的每个元素进行。 完成后，新的关联数组将替换旧的关联数组，并开始下一次迭代。 这一直持续到没有新的键来替换以前的数组为止。 前一个数组包含最长的重复项。
布雷迪代码可以在以下位置找到查找最长重复项 (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() 完成将矩阵（来自数据表）转换回列表的工作。
