logo标签列表

在二进制字符串中寻找模式

javascriptalgorithmpattern-matching
6
我正在尝试在一串二进制数字中找到重复的模式。
例如：0010010010或1110111011 = 可行
不是：0100101101 = 不可行
这些字符串长度为10位（如上所示），我猜最少需要两个“模式”的迭代。
我开始手动设置一个“库”，让程序可以与之匹配，但肯定有更好的方法使用算法？
搜索无果 - 我认为我使用的语言和术语是不正确的。
你的意思是想知道整个字符串是否可以表示为一些重复两次或更多次的较短字符串吗？你对“重复模式”的定义是什么？ - Ted Hopp
任何字符串都可以被视为具有重复模式，但其周期比位数所示的要长。 - nhahtdh
+1 如果根据问题选择语言。我想知道在这里Prolog是否能胜过JavaScript。 - Jan Turoň
1
据我所知，有62种可能性。请查看我的答案。 - גלעד ברקן
@groovy 我得到的是52而不是62？0000000000 0000100001 0001000010 0001000100 0001100011 0010000100 0010001000 0010010010 0010100101 0011000110 0011001100 0011100111 0100001000 0100010001 0100100100 0100101001 0101001010 0101010101 0101101011 0110001100 0110011001 0110101101 0110110110 0111001110 0111011101 0111101111 1000010000 1000100010 1000110001 1001001001 1001010010 1001100110 1001110011 1010010100 1010101010 1010110101 1011010110 1011011011 1011101110 1011110111 1100011000 1100110011 1100111001 1101011010 1101101101 1101110111 1101111011 1110011100 1110111011 1110111101 1111011110 1111111111 - Paddy3118
显示剩余2条评论
7个回答
2
相当有挑战性。这个函数怎么样？
function findPattern(n) {
    var maxlen = parseInt(n.length/2);
    NEXT:
    for(var i=1; i<=maxlen; ++i) {
        var len=0, k=0, prev="", sub;
        do {
            sub = n.substring(k,k+i);
            k+= i;
            len = sub.length;
            if(len!=i) break;
            if(prev.length && sub.length==i && prev!=sub) continue NEXT;
            if(!prev.length) prev = sub;
        } while(sub.length);
        var trail = n.substr(n.length-len);
        if(!len || len && trail==n.substr(0,len)) return n.substr(0,i);
    }
    return false;
}

它甚至适用于任何长度和内容的字符串。请参见这个示例

受Jack和Zim-Zam答案的启发，这里是暴力算法的列表：

var oksubs =
["001","010","011","100","101","110",
"0001","0010","0011","0100","0101","0110","0111",
"1000","1001","1010","1011","1100","1101","1110",
"00000","00001","00011","00101","00110","00111","01000",
"01001","01010","01011","01100","01101","01110","01111",
"10000","10001","10011","10101","10110","10111","11000","11001",
"11010","11011","11100","11101","11110","11111"];

感谢Jack的评论，这里有一段简短而有效的代码：
function findPattern(n) {
    var oksubs = [n.substr(0,5),n.substr(0,4),n.substr(0,3)];
    for(var i=0; i<oksubs.length; ++i) {
        var sub = oksubs[i];
        if((sub+sub+sub+sub).substr(0,10)==n) return sub;
    }
    return false;
}
1
嗨Jan，感谢您快速发布代码。我认为，可以在不使用oksubs的情况下找到模式。从原始字符串本身中取前5个、4个或3个数字。我指的是字符串长度/2。 - Jack
哦，谢谢杰克！看起来我们成功地将数学、暴力和JS结合在一起了！ - Jan Turoň
1
我的暴力方法是：
按照示例进行操作。

  1. 给定字符串: 0010010010:

  2. 创建给定字符串0010010010的可能模式列表:

    possiblePatterns = [00, 010, 0010, 00100, 01, 001, 0100, 10, 100]

  3. 将它们重复以使字符串长度>= 10

    testPattern0 = 0000000000    // 00 00 00 00 00
testPattern1 = 010010010010  // 010 010 010 010
testPattern2 = 001000100010  // 0010 0010 0010
...

  4. 并检查...

    对于每个测试模式：
    如果'0010010010'是testPattern的子串==>找到模式

    匹配字符串之一：

    testPattern2: 010010010010
givenString :   0010010010

  5. 找到的模式：

    foundPatterns = [010, 001, 100]

可以看出，这是一个可能多余的列表，因为所有模式基本上都是相同的，只是位置不同。但根据使用情况，这实际上可能是您想要的。

代码：

function findPatterns(str){
    var len = str.length;
    var possible_patterns = {};  // save as keys to prevent duplicates
    var testPattern;
    var foundPatterns = [];

    // 1) create collection of possible patterns where:
    //    1 < possiblePattern.length <= str.length/2
    for(var i = 0; i <= len/2; i++){
        for(var j = i+2; j <= len/2; j++){
            possible_patterns[str.substring(i, j)] = 0;
        }
    }

    // 2) create testPattern to test against given str where:
    //    testPattern.length >= str.length
    for(var pattern in possible_patterns){
        testPattern = new Array(Math.ceil(len/pattern.length)+1).join(pattern);
        if(testPattern.indexOf(str) >= 0){
            foundPatterns.push(pattern);
        }
    }
    return foundPatterns;
}

This text is programming-related and contains HTML code. It reads: "

==> fiddle

".
你的可能模式列表不完整：0011001100怎么样？可以从我的答案中复制模式。 - Jan Turoň
我的可能模式列表仅包含在给定示例字符串0010010010中找到的模式。我的方法根据手头的字符串动态构建可能模式列表。或者我漏掉了什么？ - tsterker
1
据我所知，长度为10的有62个模式化二进制字符串 => 2^1 + 2^2 + 2^3 + 2^4 + 2^5。下面是列出它们并匹配模式化字符串的代码：
function binComb (n){
  var answer = []
  for (var i=0; i<Math.pow(2,n);i++){
    var str = i.toString(2)
    for (var j=str.length; j<n; j++){
      str = "0" + str
    }
    answer.push(str)
  }
  return answer
}

function allCycles(){
  var answer = {}, cycled = ""
  for (var i=1; i<=5; i++){
    var arr = binComb(i)
    for (var j=0; j<arr.length; j++){
      while(cycled.length < 10){
        cycled += arr[j]
        if (10 - cycled.length < arr[j].length)
          cycled += arr[j].substr(0,10 - cycled.length)
      }
      if (answer[cycled]) 
        answer[cycled].push(arr[j])
      else answer[cycled] = [arr[j]]
      cycled = ""
    }
  }
  return answer
}

function getPattern (str){
  var patterns = allCycles()
  if (patterns[str]) 
    return patterns[str]
  else return "Pattern not found."
}

输出：
console.log(getPattern("0010010010"))
console.log(getPattern("1110111011"))
console.log(getPattern("0100101101"))
console.log(getPattern("1111111111"))

["001"]
["1110"]
Pattern not found.
["1", "11", "111", "1111", "11111"]
1
你只有2^10种模式，这个数字足够小，可以预计算所有有效字符串并将结果存储在1024元素的布尔数组中。如果一个字符串是有效的，则将其转换为整数（例如，“0000001111”=15），并在结果数组索引中存储“true”。要检查字符串是否有效，请将其转换为整数，并在预计算布尔数组中查找索引。
如果您的字符串长度超过10位，则需要更聪明地确定字符串是否有效，但由于您只有1024个字符串，所以最好懒一点。
我假设您的最小模式长度为3，因此请检查str.substring（0,2）= str.substring（3,5）= str.substring（6,8），以及str.substring（0,0）= str.substring（9,9）。如果不是这样，则尝试长度为4的模式; str.substring（0,3）= str.substring（4,7），并且str.substring（0,1）= str.substring（8,9）。如果失败，则尝试长度为5的模式。长度为6的模式将是str.substring（0,3）= str.substring（6,9），但我假设您的最大模式长度为5。 - Zim-Zam O'Pootertoot
1
  1. 维护一个2^10的数组是不会有帮助的，因为它无法指示哪些字符串具有重复模式。

  2. 要有重复模式，模式长度只能是<=5。

  3. 可以有长度为1的模式。但长度为5的模式将包含它。[步骤已编辑]

  4. 如果存在长度为2的模式，则总是存在长度为4的模式。

  5. 从(1),(2),(3)和(4)中，只需要检查长度为3、4和5的模式。

  6. 这意味着如果前三个数字与下一个三个数字匹配，则继续到字符串的结尾，否则跳转到7。

  7. 否则，将前四个数字与下一个四个数字进行匹配，如果匹配则继续到字符串的结尾，否则跳转到8。

  8. 否则，将前五个数字与下一个四个数字进行匹配，如果匹配则继续到字符串的结尾，否则跳转到9。

  9. 如果6、7、8中的一个为假，则返回失败。

如果我们将最大模式长度定义为字符串长度的一半，并从3开始比较直到字符串长度的一半，那么它可以被概括。 - Jack
1
第三步是错误和冗余的： 1111111111 的模式长度为 1，但这也是长度为 5 的模式，因此第五步的结论正确，有些运气。 - Jan Turoň
我同意。很好的发现，Jan。然而，算法仍然是有效的，正如你所说的那样。我意识到另一件事，步骤6、7和8应该按相反的顺序应用，以确保我们找到最长的模式。 - Jack
1
感谢您对暴力算法的启发，看看我的更新答案。我喜欢暴力算法获胜的时刻 :-) - Jan Turoň
0

这个答案使用了Python正则表达式，并设置了VERBOSE标志进行编译，允许带有注释和非重要空格的多行正则表达式。我还在正则表达式中使用了命名组。

该正则表达式是借助于Kodos工具开发出来的。

该正则表达式搜索长度为五、四、三的最长重复字符串。（两个重复字符是冗余的，因为它等于更长的四个字符；同样，一个重复字符也被五个字符所取代）。

import re

rawstr = r"""
(?P<r5> .{5})    (?P=r5) |
(?P<r4>(?P<_42> .{2}) .{2})   (?P=r4)   (?P=_42) |
(?P<r3>(?P<_31> .{1}) .{2})   (?P=r3){2}   (?P=_31) 
"""

matchstr = """\
1001110011
1110111011
0010010010
1010101010
1111111111
0100101101
"""

for matchobj in re.finditer(rawstr, matchstr, re.VERBOSE):
    grp, rep = [(g, r) for g, r in matchobj.groupdict().items()
                   if g[0] != '_' and r is not None][0]
    print('%r is a repetition of %r' % (matchobj.group().strip(), rep))

输出结果为：

'1001110011' is a repetition of '10011'
'1110111011' is a repetition of '1110'
'0010010010' is a repetition of '001'
'1010101010' is a repetition of '1010'
'1111111111' is a repetition of '11111'
1001110011应该显示为具有重复模式10011吗？ - cHao
@cHao，已修复。谢谢。我不小心从Kodos复制正则表达式时添加了一个额外的''。 - Paddy3118
0
在Python中（再次）但不使用正则表达式：
def is_repeated(text):
    'check if the first part of the string is repeated throughout the string'
    len_text = len(text)
    for rep_len in range(len_text // 2,  0, -1):
        reps = (len_text + rep_len) // rep_len
        if (text[:rep_len] * reps).startswith(text):
            return rep_len  # equivalent to boolean True as will not be zero
    return 0     # equivalent to boolean False

matchstr = """\
1001110011
1110111011
0010010010
1010101010
1111111111
0100101101
"""
for line in matchstr.split():
    print('%r has a repetition length of %i' % (line, is_repeated(line)))

输出：

'1001110011' has a repetition length of 5
'1110111011' has a repetition length of 4
'0010010010' has a repetition length of 3
'1010101010' has a repetition length of 4
'1111111111' has a repetition length of 5
'0100101101' has a repetition length of 0
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接