longest common sequence group

algorithm, nlp, pattern-matching, python

Solution

Here's one way:

- Sort your entries

- Determine the length of common prefix between each entry

- Group your entries by separating the list at points where the common prefix is shorter than that of the previous entry

Example implementation:

def common_count(t0, t1):
  "returns the length of the longest common prefix"
  for i, pair in enumerate(zip(t0, t1)):
    if pair[0] != pair[1]:
      return i
  return i

def group_by_longest_prefix(iterable):
  "given a sorted list of strings, group by longest common prefix"
  longest = 0
  out = []

  for t in iterable:
    if out: # if there are previous entries 

      # determine length of prefix in common with previous line
      common = common_count(t, out[-1])

      # if the current entry has a shorted prefix, output previous 
      # entries as a group then start a new group
      if common < longest:
        yield out
        longest = 0
        out = []
      # otherwise, just update the target prefix length
      else:
        longest = common

    # add the current entry to the group
    out.append(t)

  # return remaining entries as the last group
  if out:
    yield out

Example usage:

text = """
TOKYO-BLING.1 H02-AVAILABLE
TOKYO-BLING.1 H02-MIDDLING
TOKYO-BLING.1 H02-TOP
TOKYO-BLING.2 H04-USED
TOKYO-BLING.2 H04-AVAILABLE
TOKYO-BLING.2 H04-CANCELLED
WAY-VERING.1 H03-TOP
WAY-VERING.2 H03-USED
WAY-VERING.2 H03-AVAILABLE
WAY-VERING.1 H03-CANCELLED
"""

T = sorted(t.strip() for t in text.split("\n") if t)

for L in group_by_longest_prefix(T):
  print L

This produces:

['TOKYO-BLING.1 H02-AVAILABLE', 'TOKYO-BLING.1 H02-MIDDLING', 'TOKYO-BLING.1 H02-TOP']
['TOKYO-BLING.2 H04-AVAILABLE', 'TOKYO-BLING.2 H04-CANCELLED', 'TOKYO-BLING.2 H04-USED']
['WAY-VERING.1 H03-CANCELLED', 'WAY-VERING.1 H03-TOP']
['WAY-VERING.2 H03-AVAILABLE', 'WAY-VERING.2 H03-USED']

See it in action here: http://ideone.com/1Da0S

Problem

Given the following lines of text ``` TOKYO-BLING.1 H02-AVAILABLE TOKYO-BLING.1 H02-MIDDLING TOKYO-BLING.1 H02-TOP TOKYO-BLING.2 H04-USED TOKYO-BLING.2 H04-AVAILABLE TOKYO-BLING.2 H04-CANCELLED WAY-VERING.1 H03-TOP WAY-VERING.2 H03-USED WAY-VERING.2 H03-AVAILABLE WAY-VERING.1 H03-CANCELLED ``` I would like to do some parsing to generate somewhat sensible groupings. The list above can be grouped as follows ``` TOKYO-BLING.1 H02-AVAILABLE TOKYO-BLING.1 H02-MIDDLING TOKYO-BLING.1 H02-TOP TOKYO-BLING.2 H04-USED TOKYO-BLING.2 H04-AVAILABLE TOKYO-BLING.2 H04-CANCELLED WAY-VERING.2 H03-USED WAY-VERING.2 H03-AVAILABLE WAY-VERING.1 H03-TOP WAY-VERING.1 H03-CANCELLED ``` Can anyone suggest an algorithm(or some method) that can scan through a given amount of text and work out that the text can be grouped as above. Obviously each group can be further. I guess i am looking for a good solution to looking at a list of phrases and working out how best to group them by some common string sequence.

Original source