local sounddict = {}

for key, list in pairs(chatsounds.List) do
    for key, data in pairs(list) do
        sounddict[key] = ""
    end
end

local soundtree = {}
local soundtree_filekey = newproxy and newproxy() or {}
for sound_patt, sound_file in pairs(sounddict) do
    local currnode = soundtree
    for part in string.gmatch(sound_patt, "([a-z_]+)") do
        -- TODO: preprocess part to ignore case and such
        currnode[part] = currnode[part] or {}
        currnode = currnode[part]
    end
    currnode[soundtree_filekey] = string.gsub(sound_patt, " ", "_")..".wav"
end

function stuff(soundtree, phrase)
    -- TODO: preprocess phrase to ignore case and such

    local foundlist = {}

    local stack_i = 0
    local stack_eposlist = { [0] = 1 }
    local stack_nodelist = { [0] = soundtree }
    local complete, atend = false, false
    local backtrack = false
    repeat
        local spos = stack_eposlist[stack_i]
        local node = stack_nodelist[stack_i]
        stack_i = stack_i+1
        -- get next word
        --local word_s, word, word_e, mods = string.match(phrase, "()([a-z_]+)()(%p%d)*", spos, true)
        local word_s, word_e, mods = string.find(phrase, "([a-z_]+)", spos)
        if word_s then
            --print(stack_i..": "..string.sub(phrase, word_s, word_e))
            -- we have a next word
            local word = string.sub(phrase, word_s, word_e)
            local subnode = node[word] -- (you could do pattern matching here)
            if subnode then
                -- we have a pattern that matches this next word
                -- (could be first, middle or last word in pattern!)
                stack_eposlist[stack_i] = word_e+1
                stack_nodelist[stack_i] = subnode
                -- continue
            else
                -- there is no continuing pattern that matches this word
                if stack_i == 1 then
                    -- this is the first word or next unmatched word and no pattern starts with it
                    -- so jump to next word
                    stack_i = 0
                    stack_eposlist[0] = word_e+1
                else
                    -- we were matching a pattern, see what comes of it
                    -- (this word did not continue any pattern, so it's not considered)
                    backtrack = true
                end
            end
        else
            --print(stack_i..": END")
            -- there is no next word, check for patterns
            -- (last few words may be rechecked if there is no sound for their nodes)
            if stack_i == 1 then
                -- we weren't matching anything
                complete = true
            else
                atend = true
                backtrack = true
            end
        end
        if backtrack then
            -- find the longest pattern on the stack that has a sound associated
            for stack_j = stack_i-1, 1, -1 do
                -- work backwards through each word to see if it has a sound
                local node = stack_nodelist[stack_j]
                local soundfile = node[soundtree_filekey]
                if soundfile then
                    -- this word has a sound
                    table.insert(foundlist, soundfile)
                    -- TODO: handle mods here

                    if stack_j == stack_i-1 and atend then
                        -- we consumed the last word
                        complete = true
                    else
                        -- start searching for new patterns
                        stack_i = 0
                        -- resume from word after longest pattern with a sound
                        stack_eposlist[0] = stack_eposlist[stack_j]
                    end
                    -- stop backtracking
                    break
                end
            end
            backtrack, atend = false, false
        end
    until complete

    return foundlist
end

PrintTable(stuff(soundtree, "how could one man have slipped through your forces fingers time and time again how is it possible this is not some agent provocateur or highly trained assassin we are discussing gordon freeman is a theoretical physicist who had hardly earned the distinction of his ph d at the time of the black mesa incident i have good reason to believe that in the intervening years he was in a state that precluded further development of covert skills the man you have consistently failed to slow let alone capture is by all standards simply that an ordinary man how can you have failed to apprehend"))