字符串算法问题 - 单词开头

Question

我有一个问题，不太确定如何在不降低效率的情况下解决它。假设我有一个单词列表：

• Apple
• Ape
• Arc
• Abraid
• Bridge
• Braide
• Bray
• Boolean

我想要处理这个列表，并获取每个单词的前缀，例如：

• a - Apple、Ape、Arc和Abraid
• ab - Abraid
• ar - Arc
• ap - Apple和Ape
• b - Bridge、Braide、Bray和Boolean
• br - Bridge、Braide和Bray
• bo - Boolean

有什么想法吗？

- Matthew H

---

你想要生成所有开头的集合并将其与单词关联起来，还是只想能够找到某个给定开头的所有单词？ - Maciej Hehl

生成一个集合。我的做法是读取一个包含单词列表的文本文件，我想要输出类似于我上面发布的内容。Trie数据结构在处理这种情况时非常有用，但我确实需要帮助处理输入以生成输出，而不是如何存储它。 - Matthew H

Answer 1

您可以使用Trie结构。

       (root)
         / 
        a - b - r - a - i - d
       / \   \
      p   r   e
     / \   \
    p   e   c
   /
  l
 /
e

只需找到所需节点并获取其所有后代，例如，如果我想要ap-：

       (root)
         / 
        a - b - r - a - i - d
       / \   \
     [p]  r   e
     / \   \
    p   e   c
   /
  l
 /
e

- quantumSoup

Answer 2

我不知道你所说的“低效路线”是什么意思，但很明显有一个解决方案（可能就是你想到的）。Trie树看起来是这类问题的结构，但从内存消耗的角度来看代价太大（存在许多重复），而且我不确定它是否能在你的情况下加快速度。也许如果信息需要多次检索，那么内存使用会得到回报，但你的回答表明，你只想生成一次输出文件并将其存储。因此，在你的情况下，Trie树只会被生成一次就被遍历完毕了。我认为这没有意义。

我的建议是按字典顺序对单词列表进行排序，然后以最长前缀长度的次数按顺序遍历该列表。

create a dictionary with keys being strings and values being lists of strings

for(i = 1 to maxBeginnigLength)
{
    for(every word in your sorted list)
    {
        if(the word's length is no less than i)
        {
            add the word to the list in the dictionary at a key
            being the beginning of the word of length i
        }

    }

}

store contents of the dictionary to the file

- Maciej Hehl

Answer 3

也许您正在寻找类似以下内容的东西：

    #!/usr/bin/env python
    def match_prefix(pfx,seq):
        '''return subset of seq that starts with pfx'''
        results = list()
        for i in seq:
            if i.startswith(pfx):
                results.append(i)
        return results

    def extract_prefixes(lngth,seq):
        '''return all prefixes in seq of the length specified'''
        results = dict()
        lngth += 1
        for i in seq:
            if i[0:lngth] not in results:
                results[i[0:lngth]] = True
        return sorted(results.keys())

    def gen_prefix_indexed_list(depth,seq):
        '''return a dictionary of all words matching each prefix
           up to depth keyed on these prefixes'''
        results = dict()
        for each in range(depth):
            for prefix in extract_prefixes(each, seq):
                results[prefix] = match_prefix(prefix, seq)
        return results


    if __name__ == '__main__':
        words='''Apple Ape Arc Abraid Bridge Braide Bray Boolean'''.split()
        test = gen_prefix_indexed_list(2, words)
        for each in sorted(test.keys()):
            print "%s:\t\t" % each,
            print ' '.join(test[each])

这篇文章讲述了如何生成在一个单词列表中出现过的所有前缀，并且您可以指定一个数字（在此示例中为2）。然后您需要生成与每个这些前缀匹配的所有单词的索引。

我相信有更优雅的方法来实现这个功能。但是，为了快速且易于解释的方法，我只建议从显而易见的需求规格分解开始构建。如果最终结果值是给定前缀所匹配的列表，则我们首先应从输入中筛选出这些匹配的函数。如果最终结果键都是在输入中出现的1到N个前缀，则我们具有提取它们的函数。因此，我们的规格非常简单，围绕着这一点形成一个嵌套循环。

当然，这个嵌套循环可能会存在问题。通常情况下，这样的循环效率相对较低。如本程序所示，将重复C * N * N次原始列表（C是代表长度为1、2等的前缀的常数；而N是列表的长度）。

如果此分解提供了所需的语义，则可以考虑提高效率。明显的方法是在遍历列表时惰性生成字典键...对于每个单词，对于每个前缀长度，生成键...将该单词附加到存储在该键处的列表/值中...然后继续下一个单词。

仍然有一个嵌套循环，但这是每个关键字/前缀长度的短循环。该替代设计的优点在于，我们可以遍历来自任何可迭代对象的单词列表，而不仅仅是内存中的列表。因此，我们可以遍历文件的行、从数据库查询生成的结果等---而不会出现保留整个原始单词列表所需的内存开销的问题。

当然，我们仍然将字典存储在内存中。但是我们也可以改变它，将逻辑与输入和存储分离。当我们将每个输入附加到各种前缀/键值时，我们不关心它们是否是字典中的列表、文件集合中的行，还是从DBM或其他键/值存储中提取并推回的值（例如某些类型的CouchDB或其他“noSQL clustered/database”）。

实现留给读者作为练习。

- Jim Dennis

Answer 4

使用这个PHP trie实现可以让你完成大约50%的工作。它有一些你不需要的东西，也没有“按前缀搜索”的方法，但你可以很容易地自己编写一个。

$trie = new Trie();

$trie->add('Apple',   'Apple');
$trie->add('Ape',     'Ape');
$trie->add('Arc',     'Arc');
$trie->add('Abraid',  'Abraid');
$trie->add('Bridge',  'Bridge');
$trie->add('Braide',  'Braide');
$trie->add('Bray',    'Bray');
$trie->add('Boolean', 'Boolean');

它构建了这样的一个结构：

Trie Object
(
  [A] => Trie Object
  (
    [p] => Trie Object
    (
      [ple] => Trie Object
      [e] => Trie Object
    )

    [rc] => Trie Object
    [braid] => Trie Object
  )

  [B] => Trie Object
  (
    [r] => Trie Object
    (
      [idge] => Trie Object
      [a] => Trie Object
      (
        [ide] => Trie Object
        [y] => Trie Object
      )
    )

    [oolean] => Trie Object
  )
)

- John Kugelman

Answer 5

如果这些单词存储在数据库（Access、SQL）中，而你想要检索所有以“br”开头的单词，你可以使用以下代码：

Table Name: mytable
Field Name: mywords

"Select * from mytable where mywords like 'br*'"  - For Access - or

"Select * from mytable where mywords like 'br%'"  - For SQL

- Claudio