Android中快速，低功耗/cpu字符串匹配 [英] Rapid, low power/cpu string matching in Android

问题描述

我正在开发一个应用程序，该应用程序需要语音输入，并将该输入与清单中的已知项进行匹配.

I'm working on an app that takes voice input, and matches that input to known items in a manifest.

清单中的每个项目都有一个别名列表，以便具有长标题的项目可以与较短的名称匹配.

Each item in the manifest has a list of aliases, so that items with long titles can be matched to shorter names.

例如:

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

然后以以下方式加载到内存中:

And then loaded into memory as:

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

然后通过以下方式匹配:

And then matched through:

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;
        }
    }
}

这对于原型中包含25个项目的测试批次非常有用，但最终它将需要在手机上尽可能接近实时地处理5,000-10,000个项目.

This is working great on a test batch of twenty five items in the prototype, but eventually it will need to handle 5,000-10,000 items in as close to real time as possible on a phone.

核心问题:

假设我可以在内存中保存10,000个这些项目(示例时钟大约为64 KB，因此对于10,000个项目，总共不到一兆字节)，那么在android上用来将这些对象存储在内存中的最佳集合是什么，以及用数据填充该对象然后找到匹配元素的最快方法是什么?

Assuming I can hold 10,000 of these items in memory (the sample clocks in about 64 kilobytes, so less than a megabyte in total for 10,000 items), what is the best collection to use on android to store these objects in memory, and what is the fastest way to populate that object with data, and then find matching elements?

推荐答案

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

You can easily do this with a Map assuming no duplicate aliases or product names. Kotlin version is:

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没有任何意义.集合没有意义，因为您只能说它是否存在"，而不能说它匹配哪件事".地图将从任何内容转换为原始的Product，您可以从中获取名称.

A Trie does not make sense unless you are doing prefix matches. A Set makes no sense because you can only tell "does it exist" and not "which thing is it that matches". A Map will go from anything to the original Product from which you can get the name.

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

Also, your brute-force matching algorithm re-written in Kotlin is in an answer to your other question: https://stackoverflow.com/a/52565549/3679676

这篇关于Android中快速，低功耗/cpu字符串匹配的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！