16

I'm working with a large list containing integers and I would like to do some pattern matching on them (like finding certain sequences). Regular expressions would be the perfect fit, except that they always seem to only handle lists of characters, a.k.a. strings. Is there any library (in any language) that can handle lists of an arbitrary type?

I'm aware that I could convert my integer list into a string and then do a normal regular expression search but that seems a bit wasteful and inelegant.

edit:

My requirements are fairly simple. No need for nested lists, no need for fancy character classes. Basically I'm just interested in occurrences of sequences that can get pretty complicated. (e.g. something like "[abc]{3,}.([ab]?[^a]{4,7})" etc. where a,b,c are integers). This should be possible to generalize over any type which can be checked for equality. For an enumerable type you could also get things like "[a-z]" to work.

6
  • 1
    Could you post some examples?
    – Bart Kiers
    Nov 29, 2010 at 11:32
  • +1 for the interesting question. I had a look and was disappointed to see Scala'a regex only work with Strings - the standard library there is usually quite generalised. I look forward to some answers Nov 29, 2010 at 11:37
  • How big is the integers? If 21-bits or below, you could convert each to a Unicode code point.
    – leppie
    Nov 29, 2010 at 12:05
  • @leppie: I could, but as I state it's hardly an elegant solution to convert it into a string and then back again.
    – pafcu
    Nov 29, 2010 at 12:17
  • @Paddy: About 100.000 elements. Converting such a list is not very time consuming, but I'll be doing it many times.
    – pafcu
    Nov 29, 2010 at 12:35

7 Answers 7

2

Regular expressions match only strings, by definition.

Of course, in theory you could construct an equivalent grammar, say for lists of numbers. With new tokens like \e for even numbers, \o for odd numbers, \s for square numbers, \r for real numbers etc., so that

[1, 2, 3, 4, 5, 6]

would be matched by

^(\o\e)*$

or

[ln(3), math.pi, sqrt(-1)]

would be matched by

^\R*$

etc. Sounds like a fun project, but also like a very difficult one. And how this could be expanded to handle arbitrary lists, nested and all, is beyond me.

3
  • I don't need anything so integer-specific. I actually just want to match repeats of various lengths
    – pafcu
    Nov 29, 2010 at 12:19
  • Finite lists of int (32 bit) are strings (words) in the sense of formal languages. Therefore, regular expressions are in theory applicable in this case. Nov 29, 2010 at 22:38
  • @Christian: That's certainly correct. pafcu was asking about lists of arbitrary types, though, and edited his question to clarify his requirements after I had answered. Dec 1, 2010 at 11:17
1

Some of the regex syntax generalize to generic sequences. Also, to be able to specify any object, strings is not the best medium for the expression themselves.

"Small" example in python:

def choice(*items):
  return ('choice',[value(item) for item in items])

def seq(*items):
  return ('seq',[value(item) for item in items])

def repeat(min,max,lazy,item):
  return ('repeat',min,max,lazy,value(item))

def value(item):
  if not isinstance(item,tuple):
    return ('value',item)
  return item

def compile(pattern):
  ret = []
  key = pattern[0]
  if key == 'value':
    ret.append(('literal',pattern[1]))
  elif key == 'seq':
    for subpattern in pattern[1]:
      ret.extend(compile(subpattern))
  elif key == 'choice':
    jumps = []
    n = len(pattern[1])
    for i,subpattern in enumerate(pattern[1]):
      if i < n-1:
        pos = len(ret)
        ret.append('placeholder for choice')
        ret.extend(compile(subpattern))
        jumps.append(len(ret))
        ret.append('placeholder for jump')
        ret[pos] = ('choice',len(ret)-pos)
      else:
        ret.extend(compile(subpattern))
    for pos in jumps:
      ret[pos] = ('jump', len(ret)-pos)
  elif key == 'repeat':
    min,max,lazy,subpattern = pattern[1:]
    for _ in xrange(min):
      ret.extend(compile(subpattern))
    if max == -1:
      if lazy:
        pos = len(ret)
        ret.append('placeholder for jump')
        ret.extend(compile(subpattern))
        ret[pos] = ('jump',len(ret)-pos)
        ret.append(('choice',pos+1-len(ret)))
      else:
        pos = len(ret)
        ret.append('placeholder for choice')
        ret.extend(compile(subpattern))
        ret.append(('jump',pos-len(ret)))
        ret[pos] = ('choice',len(ret)-pos)
    elif max > min:
      if lazy:
        jumps = []
        for _ in xrange(min,max):
          ret.append(('choice',2))
          jumps.append(len(ret))
          ret.append('placeholder for jump')
          ret.extend(compile(subpattern))
        for pos in jumps:
          ret[pos] = ('jump', len(ret)-pos)
      else:
        choices = []
        for _ in xrange(min,max):
          choices.append(len(ret))
          ret.append('placeholder for choice')
          ret.extend(compile(subpattern))
          ret.append(('drop,'))
        for pos in choices:
          ret[pos] = ('choice',len(ret)-pos)
  return ret

def match(pattern,subject,start=0):
  stack = []
  pos = start
  i = 0
  while i < len(pattern):
    instruction = pattern[i]
    key = instruction[0]
    if key == 'literal':
      if pos < len(subject) and subject[pos] == instruction[1]:
        i += 1
        pos += 1
        continue
    elif key == 'jump':
      i += instruction[1]
      continue
    elif key == 'choice':
      stack.append((i+instruction[1],pos))
      i += 1
      continue
    # fail
    if not stack:
      return None
    i,pos = stack.pop()
  return pos

def find(pattern,subject,start=0):
  for pos1 in xrange(start,len(subject)+1):
    pos2 = match(pattern,subject,pos1)
    if pos2 is not None: return pos1,pos2
  return None,None

def find_all(pattern,subject,start=0):
  matches = []
  pos1,pos2 = find(pattern,subject,start)
  while pos1 is not None:
    matches.append((pos1,pos2))
    pos1,pos2 = find(pattern,subject,pos2)
  return matches

# Timestamps: ([01][0-9]|2[0-3])[0-5][0-9]
pattern = compile(
  seq(
    choice(
      seq(choice(0,1),choice(0,1,2,3,4,5,6,7,8,9)),
      seq(2,choice(0,1,2,3)),
    ),
    choice(0,1,2,3,4,5),
    choice(0,1,2,3,4,5,6,7,8,9),
  )
)

print find_all(pattern,[1,3,2,5,6,3,4,2,4,3,2,2,3,6,6,5,3,5,3,3,2,5,4,5])
# matches: (0,4): [1,3,2,5]; (10,14): [2,2,3,6]

A few points of improvement:

  • More constructs: classes with negation, ranges
  • Classes instead of tuples
0

If you really need a free grammar like in regular expressions, then you have to go a way as described in Tim's answer. If you only have a fixed number of patterns to search for, then the easiest and fastest way is to write your own search/filter functions.

0

Interesting problem indeed.

Lateral thinking: download the .Net Framework Source code, lift the Regex source code and adapt it to work with integers rather than characters.

Just an idea.

0

Well, Erlang has pattern matching (of your type) built right in. I did something similar once in Ruby - a bit of probably not too well performing hackery, see http://radiospiel.org/0x16-its-a-bird

2
  • Based on the example on your page it doesn't seem like it can be used for such complicated matching like "((between 3 and 7 occurrences of 7) OR exactly one 1) followed by (an optional 9) followed by (three numbers that are not 5 or 7) followed by ..."
    – pafcu
    Nov 30, 2010 at 12:53
  • This does not match the OPs request perfectly, no. I wanted to hint to Erlang's pattern matching, and show, that it is possible to do similar things with ruby, without Regexes.
    – radiospiel
    Dec 1, 2010 at 12:16
0

Clojure since version 1.9 has clojure.spec in the standard library, which can do exactly that and more. For example to describe a sequence of odd numbers that may end with one even number you'd write:

(require '[clojure.spec.alpha :as s])
(s/def ::odds-then-maybe-even (s/cat :odds (s/+ odd?)
                                     :even (s/? even?)))

Then to get matching subsequences you'd do this:

(s/conform ::odds-then-maybe-even [1 3 5 100])
;;=> {:odds [1 3 5], :even 100}

(s/conform ::odds-then-maybe-even [1])
;;=> {:odds [1]}

And to find out why a sequence doesn't match your definition:

(s/explain ::odds-then-maybe-even [100])
;; In: [0] val: 100 fails spec: ::odds-then-maybe-even at: [:odds] predicate: odd?

See full documentation with examples at https://clojure.org/guides/spec

-2

You can try pamatcher, it's a JavaScript library that generalize the notion of regular expressions for any sequence of items (of any type).

An example for "[abc]{3,}.([ab]?[^a]{4,7})" pattern matching, where a, b, c are integers:

var pamatcher = require('pamatcher');

var a = 10;
var b = 20;
var c = 30;

var matcher = pamatcher([
  { repeat: 
      { or: [a, b, c] }, 
    min: 3
  },
  () => true,
  { optional: 
    { or: [a, b] } 
  },
  { repeat: (i) => i != a,
    min: 4,
    max: 7
  }
]);

var input = [1, 4, 8, 44, 55];
var result = matcher.test(input);
if(result) {
  console.log("Pattern matches!");
} else {
  console.log("Pattern doesn't match.");
}

Note: I am the creator of this library.

4
  • Seems cool. I don't know why you are downvoted. Is there a reason you can't use something more like the traditional syntax for making the regular expressions? Also, there are a few typos on the pamatcher.js.org page you may want to fix.
    – pafcu
    Dec 4, 2015 at 8:21
  • I guess I am downvoted because, at my first revision answer, I forgot to tell "I am the creatir if this library" and I didn't include any examples. But I edited my answer, however downvote wasn't removed.
    – pmros
    Dec 4, 2015 at 11:58
  • I could translate some kind of string-based-like-regex pattern to actual expression patterns but this expressions are more powerful because they can include any predicate (not only equality). I can't find any typos at pamatcher.js.org but website is hosted at github pages so you can fix them at github, if you like.
    – pmros
    Dec 4, 2015 at 12:11
  • I removed my DV. Please note that voters are not notified when you change your answer. It was coincidence that brought me back here
    – Tim
    Dec 8, 2015 at 9:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.