2

我需要检查数百万个字符串的缩写，并用完整版本替换它们。由于数据原因，仅应替换以逗号结尾的缩写词。字符串可以包含多个缩写。

我有一个包含 Abbreviation->Fullversion 对的查找表，它包含大约 600 对。

我当前的设置看起来像这样。在启动时，我使用 Jackson 从一个 csv 文件创建一个 ShortForm 实例列表，并将它们保存在一个单例中：

public static class ShortForm{
    public String fullword;
    public String abbreviation;
}

List<ShortForm> shortForms = new ArrayList<ShortForm>();
//csv code ommited

还有一些使用列表的代码

for (ShortForm f: shortForms){
    if (address.contains(f.abbreviation+","))
        address = address.replace(f.abbreviation+",", f.fullword+",");
}

现在这可行，但速度很慢。有什么办法可以加快速度吗？第一步是加载带有逗号的 ShortForm 对象，但我还能做什么？

======更新 更改代码以相反的方式工作。将字符串拆分为单词并检查集合以查看字符串是否为缩写。

    StringBuilder fullFormed = new StringBuilder();
    for (String s: Splitter.on(" ").split(add)){
        if (shortFormMap.containsKey(s))
            fullFormed.append(shortFormMap.get(s));
        else
            fullFormed.append(s);
        fullFormed.append(" ");
    }

    return fullFormed.toString().trim();

测试表明这比原始方法快 13 倍以上。干杯达夫康！

4

3 回答 3

2

如果你跳过contains()部分已经会快一点:)

于 2013-10-11T08:11:41.010 回答
1

我想我会用 HashMap 来做到这一点。键是缩写，值是全称。然后只需在字符串中搜索逗号，然后查看逗号前面的文本是否在字典中。您可能可以一次将所有替换映射到一个字符串中，然后在此之后进行所有替换。

这使得每次查找 O(1) 总共 O(n) 查找，其中 n 是找到的缩写的数量，我认为可能没有更有效的方法。

于 2013-10-11T08:37:38.583 回答
1

真正能提高性能的是使用比简单数组更好的数据结构来存储 ShortForms。所有的shortForms都可以按缩写字母顺序存储。因此，您可以将查找时间从 O(N) 减少到看起来更像二进制搜索的时间。

我以前没有使用过它，但也许标准库的 SortedMap 符合要求，而不是使用自定义对象： http://docs.oracle.com/javase/7/docs/api/java/util/SortedMap。 html

这就是我的想法：

  • 将缩写/全词对放入 TreeMap
  • 将地址标记为单词。
  • 检查每个单词，看它是否是 TreeMap 中的键
  • 如果是则更换
  • 将更正后的令牌重新组合在一起作为地址
于 2013-10-11T08:11:47.527 回答