java - Android 中快速、低功耗/CPU 字符串匹配

Question

我正在开发一个应用程序，该应用程序接受语音输入，并将该输入与 list 中的已知项目进行匹配。

list 中的每个项目都有一个别名列表，以便长标题的项目可以与较短的名称相匹配。

例如:

class Product
{
  itemname: "Old Stinky's Western Kentucky Big Rig Polish",
  aliases: ["old stinky", "other alias"]
}

然后加载到内存中:

public List<Product> Collection;
Collection.Add(alltheproducts);

然后通过以下方式进行匹配:

public String isProductOrAlias(String lowertext) 
for (Product p: products.Collection) {
    if(lowertext.equals(p.name.toLowerCase()))
        return p.name;
    if(p.aliases != null) {
        for (String s: p.aliases) {
            if(lowertext.equals(s.toLowerCase()))
                return p.name;
        }
    }
}

这对于原型(prototype)中 25 个项目的测试批处理效果很好，但最终需要在手机上尽可能实时地处理 5,000-10,000 个项目。

核心问题:

假设我可以在内存中保存 10,000 个这些项目(样本时钟约为 64 KB，因此 10,000 个项目总共不到 1 MB)，在 Android 上使用什么集合来将这些对象存储在内存中，用数据填充该对象然后找到匹配元素的最快方法是什么？

Answer 1

假设没有重复的别名或产品名称，您可以使用Map轻松完成此操作。 Kotlin 版本是:

data class Product(val name: String, val aliases: Array<String>)

fun test() {
    val products = listOf<Product>( ... )

    // Do this once, create a map from name and aliases to the product
    val productIndex = products.asSequence().flatMap { product ->
        val allKeys = sequenceOf(product.name) + product.aliases
        allKeys.map { it.toLowerCase() to product }
    }.toMap() 
    // now name => product and each alias => product are mapped in productIndex

    val matchingProduct = productIndex["something"] // search lower case name

    println(matchingProduct?.name ?: "<not found>")
}

除非进行前缀匹配，否则 Trie 没有意义。 Set 没有任何意义，因为你只能判断“它是否存在”，而不能判断“哪个东西匹配”。 map 将从任何内容到原始的 Product，您可以从中获取名称。

此外，您用 Kotlin 重写的暴力匹配算法是对您的其他问题的回答:https://stackoverflow.com/a/52565549/3679676