Daniel Daniel - 6 months ago 9
Swift Question

Search strings for certain words or prhases

I have over 1000 strings and a fixed array of [sub]strings. I'd like to know which of my strings contain any of the substrings. (Again, the substrings are constant.) I'd like to also make sure that words are matched, not the strings.

What's the most efficient way of doing this? Can I do better than doing 1000 times an indexOf() on all substrings?

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

Consider this. The good of this solution is having fixedSearchStrings prepared you can buid the index only once and then effectively reuse it.

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)

RESULTS IN

nil
"knock on the door"
Comments