string - 搜索字符串中的某些单词或短语

Question

我有超过 1000 个字符串和一个固定的 [sub] 字符串数组。我想知道我的哪个字符串包含任何子字符串。 (同样，子字符串是不变的。)我还想确保单词匹配，而不是字符串匹配。

最有效的方法是什么？我能比对所有子字符串执行 1000 次 indexOf() 更好吗？

let str1 = "During the winter holiday I'll go skiing."
let str2 = "Do knock on the door or chime the bell"    
let fixedSearchStrings = ["ring the", "chime the bell", "knock on the door", "knock on the window"]
str1.indexOf(fixedSearchStrings)   // returns nil. "During" is not the word "ring".
str2.indexOf(fixedSearchStrings)   // returns 2. "knock on the door" substring found, no need to check further in the sentence.

Answer 1

考虑一下这一点。这个解决方案的优点是准备好fixedSearchStrings，您只需构建索引一次，然后有效地重用它。

class Index
{
    var indexes: [String: Index]
    var terminated: Bool = false

    init() {
        indexes = [String: Index]()
    }

    func searchFor(keywords: [String]) -> String? {

        var ws = keywords
        if ws.count > 0 {

            let word = ws.removeFirst()
            if let i = indexes[word] {

                if i.terminated {
                    return word
                } else {

                    if let rval = i.searchFor(ws) {
                        return "\(word) \(rval)"
                    }
                }
            }
        }
        return nil
    }

    func add(words: [String]) {

        var ws = words
        if ws.count > 0 {
            let word = ws.removeFirst()
            var index: Index!
            if let i = indexes[word] {
                index = i
            } else {
                let i = Index()
                indexes[word] = i
                index = i
            }
            index.add(ws)
            index.terminated = ws.count == 0 || index.terminated
        }
    }
}

class SearchEngine {

    var index: Index!

    func buildIndex(keywords: [String]) {

        index = Index()
        for keyword in keywords {
            let words = keyword.characters.split(" ").map(String.init)
            index.add(words)
        }
    }

    func firstEntryIn(string: String) -> String? {

        var strArr = string.characters.split(" ").map(String.init)
        var rval: String?
        while strArr.count > 0 {

            if let r = index.searchFor(strArr) {
                rval = r
                break
            }
            strArr.removeFirst()
        }
        return rval
    }
}

let str1 = "During the winter holiday I'll go skiing."
let str2 = "Do knock on the door or chime the bell"
let fixedSearchStrings = ["ring the", "chime the bell", "knock on the door", "knock on the window"]

let se = SearchEngine()
se.buildIndex(fixedSearchStrings)
se.firstEntryIn(str1)
se.firstEntryIn(str2)

结果

nil
"knock on the door"