寻找多个共同起始字符串

Question

我有一列字符串，其中一个或多个子字符串具有共同的起始字符串。我希望有一个函数，可以将原始的字符串列表作为输入，并返回所有共同起始字符串的列表。在我的情况下，我还知道每个共同前缀必须以给定的分隔符结尾。以下是我所说的输入数据类型的示例（忽略任何颜色突出显示）：

Population of metro area / Portland
Population of city / Portland
Population of metro area / San Francisco
Population of city / San Francisco
Population of metro area / Seattle
Population of city / Seattle

这里的分隔符是 /，常见的起始字符串是都市区人口和城市人口。也许分隔符并不重要，但我想强调的是，我不希望只返回一个结果，即普遍通用的起始字符串人口；我也不希望返回常见子字符串都市区人口 / S和城市人口 / S。

该算法的最终使用目的是按照它们的公共前缀将字符串分组。例如，上面的列表可以重新结构化成一个层次结构，消除冗余信息，如下所示：

Population of metro area
    Portland
    San Francisco
    Seattle
Population of city
    Portland
    San Francisco
    Seattle

我正在使用Python，但任何语言的伪代码都可以。

编辑 正如Tom Anderson所指出的那样，原始问题可以轻松地简化为仅仅是将字符串拆分并使用哈希来按前缀分组。我最初认为这个问题可能更加复杂，因为在实践中有时会遇到具有嵌入式分隔符的前缀，但我意识到这也可以通过仅对一个右拆分进行限制来解决。

- Abiel

---

您希望如何处理“San Francisco”和“San Antonio”在分组中的情况？ - retracile

Answer 1

这不就是在字符串上循环，按分隔符分割它们，然后通过第一半将第二半分组吗？像这样：

def groupByPrefix(strings):
    stringsByPrefix = {}
    for string in strings:
            prefix, suffix = map(str.strip, string.split("/", 1))
            group = stringsByPrefix.setdefault(prefix, [])
            group.append(suffix)
    return stringsByPrefix

一般来说，如果您正在寻找字符串前缀，解决方案是将字符串放入trie中。具有多个子节点的任何分支节点都是最大公共前缀。但是，您的需求比那更加限制。

- Tom Anderson

---

为什么要使用这个而不是 itertools.groupby？ - Austin Marshall

Answer 2

d = collections.defaultdict(list)

for place, name in ((i.strip() for i in line.split('/'))
                    for line in text.splitlines()):
    d[place].append(name)

所以d将会是一个类似于字典的数据结构：

{'Population of city':
       ['Portland',
        'San Francisco',
        'Seattle'],
 'Population of metro area':
       ['Portland',
        'San Francisco',
        'Seattle']}

如果您确定文本周围没有额外的空格，可以使用 line.split(' / ') 替换 (i.strip() for i in line.split('/')。

- JBernardo

Answer 3

使用csv.reader和itertools.groupby，将“/”作为分隔符并按第一列进行分组：

for key, group in groupby(sorted(reader(inp, delimiter='/')), key=lambda x: x[0]):
    print key
    for line in group:
        print "\t", line[1]

- Austin Marshall

Answer 4

这并不是很通用，但可能能满足你的需求：

def commons(strings):
    return set(s.split(' / ')[0] for s in strings)

为了避免重新对数据进行分组：

def group(strings):
    groups = {}
    for s in strings:
        prefix, remainder = s.split(' / ', 1)
        groups.setdefault(prefix, []).append(remainder)
    return groups

- retracile