I'd look for a library and not write one from scratch. Lucene [1] and OpenFST [2] are great implementations. I haven't used C#, so I don't know if bindings exist or not.

Also you may find this talk useful [3] (Particularly slide 11).

Great write up by the way. Really thorough on the benchmarking!

[1] https://lucene.apache.org/core/4_1_0/core/org/apache/lucene/...

[2] http://www.openfst.org/twiki/bin/view/FST/WebHome

[3] https://www.slideshare.net/lucenerevolution/text-tagging-wit...