代码之家 › 专栏 › 技术社区 › dr. evil

如何像Excel一样发现和分析类似的模式?

fuzzy similarity design-patterns algorithm

6

dr. evil · 技术社区 · 16 年前

例如

类型。..

测试2
测试3

Excel将继续执行以下操作:

测试5
测试n。。。

测试黄色某物
测试红色的东西

测试-[动态]-某物

用其他颜色继续[动态]是另一回事,我现在真的不在乎。我最感兴趣的是检测模式中的[DDYNAMIC]部分。

我需要从大量的池条目中检测到这一点。假设你有10000个具有这种模式的字符串,你想根据相似性对这些字符串进行分组,并检测文本的哪个部分在不断变化([DDYNAMIC])。

例如:

test_[动态]

4 回复 | 直到 16 年前

1

2

Il-Bhima 16 年前

<const1><dynamic1><const2><dynamic2>.... longest common subsequence 您提供的示例字符串。例如,如果我有 test-123-abc 和 test-48953-defg test- 和 - 动态部分将是LCS结果之间的间隙。然后,您可以在适当的数据结构中查找动态部分。

找到2个以上字符串的LCS的问题非常昂贵,这将是您问题的瓶颈。以牺牲准确性为代价,你可以使这个问题变得易于处理。例如,您可以在所有字符串对之间执行LCS,并将具有相似LCS结果的字符串集组合在一起。然而,这意味着一些模式将无法被正确识别。

当然,如果你能对字符串施加进一步的限制,所有这些都是可以避免的,就像Excel一样,它似乎只允许表单的模式 <const><dynamic> .

2

0

Niko 16 年前

找到[动态]没什么大不了的,你可以用2个字符串来做到这一点——从头开始,当它们开始不相等时停止,从最后开始做同样的事情,瞧,你就得到了你的[动态]

类似于(伪代码-有点):

String s1 = 'asdf-1-jkl';
String s2= 'asdf-2-jkl';
int s1I = 0, s2I = 0;
String dyn1, dyn2;
for (;s1I<s1.length()&&s2I<s2.length();s1I++,s2I++)
  if (s1.charAt(s1I) != s2.charAt(s2I))
    break;
int s1E = s1.length(), s2E = s2.length;
for (;s2E>0&&s1E>0;s1E--,s2E--)
  if (s1.charAt(s1E) != s2.charAt(s2E))
    break;
dyn1 = s1.substring(s1I, s1E);
dyn2 = s2.substring(s2I, s2E);

关于你的10k数据集。你需要用每个组合来调用这个(或者可能是一个更优化的版本),以找出你的模式(10k x 10k调用)。然后按模式对结果进行排序(即保存开始和结束并按这些字段排序)

3

0

Florian 16 年前

我认为你需要的是计算类似 Levenshtein distance ,找到一组相似的字符串,然后在每组相似的字符串中,用典型的类diff算法识别动态部分。

4

0

Saltash Matt Saltash Matt 16 年前

不管你信不信,谷歌文档可能比excel更适合这类事情。