string - 如何找到最短的文本，如自动完成？

我有一个字符串列表，我想找到最短的唯一方式来识别它们。它有点像自动完成，但对于给定的集合，将始终是最短的可识别方式。

举个例子。

PA  for Paddington
PE  for Penryn
PLO for Plymouth
PLP for Plympton
PO  for Portsmouth
Q   for Quebec

我有几千个名字(它们不是城市，而是程序名称)。

我需要一个相对较短的顺序(对于上面的列表，键和值都是有序的)。

任何用于此的技术/算法都会很有用。

我知道我必须编写代码(使用 PHP)，但只要我能理解算法，我就很高兴。

我想我必须按照它们目前的状态构建一棵值树，然后开始一次一个字符地导航该树，忽略具有单个选项的序列(例如 Plymouth/Plympton 中的 L 和 Y)。

所以，从魁北克的 Q 开始，我发现在整个树中，所有后续字母都只使用一次，所以在那个阶段 Q 就足够了。

最佳答案

您可以首先创建一个哈希表结构，该结构将可能的子字符串映射到以该子字符串开头的所有名称的列表。这最终可能会成为一个非常大的数据结构，但是由于您可以在到达唯一子字符串的那一刻短路，因此可以防止大小变得不合理地大。下面是一个使用 C# 的例子:

var names = new[]{
"Paddington",
"Penryn",
"Plymouth",
"Plympton",
"Portsmouth",
"Quebec"};
// First, for any given subsequence, find groups of names that
// start with it.
var groups = new Dictionary<string, List<string>>();
ILookup<string, string> newGroups;
List<string> namesToProcess = names.ToList();
int i = 0;
do
{
    // Stop looking at names once we're getting substrings too long for them.
    namesToProcess = namesToProcess.Where(n => n.Length >= i).ToList();
    newGroups = namesToProcess.ToLookup(n => n.Substring(0, i));
    foreach(var g in newGroups)
    {
        groups.Add(g.Key, g.ToList());
    }
    // stop looking at names once we find that they're the only ones
    // matching a given substring.
    namesToProcess = namesToProcess
        .Except(newGroups
            .Where(g => g.Count() == 1)
            .Select(g => g.Single()))
        .ToList();
    i++;
} while (newGroups.Any());

既然可以轻松查找与给定子序列匹配的项目数，那么为任何给定名称构建最佳代码是一项简单的任务。您从一个空字符串开始，然后添加每个字母，以帮助您缩小可能性的数量:

// Now build the best code to use for each name
var codeNamePairs = names.ToDictionary(n =>
{
    var sb = new StringBuilder();
    for(int j = 0; j < n.Length; j++)
    {
        var prefix = n.Substring(0, j+1);
        var withSamePrefix = groups[prefix];
        // Only add the next letter if it helps to narrow down
        // the possibilities
        if(withSamePrefix.Count != groups[sb.ToString()].Count)
        {
            sb.Append(n[j]);
        }
        if(withSamePrefix.Count == 1)
        {
            // Once we reach a prefix that's unique to this name,
            // then we know we've built the code we want.
            break;
        }
    }
    return sb.ToString();
});

我不确定将代码转换为 PHP 的难易程度，但希望我能很好地传达总体思路。

关于string - 如何找到最短的文本，如自动完成？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/30126909/