3

给定以下文本行

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

我想做一些解析来生成一些合理的分组。上面的列表可以分组如下

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

任何人都可以建议一种算法（或某种方法），它可以扫描给定数量的文本并计算出可以如上所述对文本进行分组。显然每个组都可以更进一步。我想我正在寻找一个很好的解决方案来查看短语列表并找出如何最好地按一些常见的字符串序列对它们进行分组。

4

4 回答 4

5

这是一种方法：

  1. 对您的条目进行排序
  2. 确定每个条目之间公共前缀的长度
  3. 通过在公共前缀比上一个条目短的点处分隔列表来对条目进行分组

示例实现：

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

示例用法：

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

这会产生：

['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']

在此处查看实际操作：http: //ideone.com/1Da0S

于 2012-06-29T14:37:22.430 回答
1

您可以用空格分割每个字符串，然后制作一个dict.

我是这样做的：

f = open( 'hotels.txt', 'r' )   # read the data
f = f.readlines()               # convert to a list of strings (with newlines)
f = [ i.strip() for i in f ]    # take off the newlines
h = [ i.split(' ') for i in f ] # split using whitespace
                                # now h is a list of lists of strings

keys = [ i[0] for i in h ]      # keys = ['TOKYO-BLING.1','TOKYO-BLING.1',...]
keys = list( set( keys ) )      # take out redundant elements

d = dict()                      # start a dict
for i in keys:                  # initialize dict with empty lists
    d[i] = list()               # (one for each key)

for i in h:                     # for each list in h, append a suffix
    d[i[0]].append(i[1])        # to the appropriate prefix (or key)

这会产生：

{'TOKYO-BLING.1': ['H02-AVAILABLE', 'H02-MIDDLING', 'H02-TOP'],\
 'TOKYO-BLING.2': ['H04-USED', 'H04-AVAILABLE', 'H04-CANCELLED'],\
 'WAY-VERING.1': ['H03-TOP', 'H03-CANCELLED'],\
 'WAY-VERING.2': ['H03-USED', 'H03-AVAILABLE']}
于 2012-06-29T14:00:21.163 回答
1

这是我的，开始时间较短：

import os

def prefix_groups(data):
    """Return a dictionary of {prefix:[items]}."""
    lines = data[:]
    groups = dict()
    while lines:
        longest = None
        first = lines.pop()
        for line in lines:
            prefix = os.path.commonprefix([first, line])
            if not longest:
                longest = prefix
            elif len(prefix) > len(longest):
                longest = prefix
        if longest:
            group = [first]
            rest = [item for item in lines if longest in item]
            [lines.remove(item) for item in rest]
            group.extend(rest)
            groups[longest] = group
        else:
            # Singletons raise an exception
            raise IndexError("No prefix match for {}!".format(first))
    return groups

if __name__ == "__main__":
    from pprint import pprint
    data = """
    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
    """
    data = [line.strip() for line in data.split('\n') if line.strip()]
    groups = prefix_groups(data)
    pprint(groups)

输出：

{'TOKYO-BLING.1 H02-': ['TOKYO-BLING.1 H02-AVAILABLE',
                        'TOKYO-BLING.1 H02-MIDDLING',
                        'TOKYO-BLING.1 H02-TOP'],
 'TOKYO-BLING.2 H04-': ['TOKYO-BLING.2 H04-USED',
                        'TOKYO-BLING.2 H04-AVAILABLE',
                        'TOKYO-BLING.2 H04-CANCELLED'],
 'WAY-VERING.1 H03-': ['WAY-VERING.1 H03-TOP', 'WAY-VERING.1 H03-CANCELLED'],
 'WAY-VERING.2 H03-': ['WAY-VERING.2 H03-USED', 'WAY-VERING.2 H03-AVAILABLE']}
于 2012-09-21T23:43:26.847 回答
0

通用后缀树或后缀数组可以工作

于 2012-07-04T01:45:44.440 回答