5 ms·

If this was not frowned upon on StackOverflow, the correct answer would recommend a commercial API. That said, if I were to implement this from scratch, I woul

If this was not frowned upon on StackOverflow, the correct answer would recommend a commercial API. That said, if I were to implement this from scratch, I would not start with a positive list of cities. Rather, I would implement a couple of patterns like: "from X to Y", "X to Y", ""to Y from X". But invariably there are going to be ambiguities. How do you deal with a city called "from to" :-D? How to you parse "from from to to to from"? I'd probably tokenize it using place lists, like "from (from to) to (to from)" "from (from to) (to to) from" "from from (to to) to from" ... and then, maybe assigning probabilities to each parsing, decide that the first one is most likely. A side comment, for someone like me who isn't an NLP expert, it seems strange that there are no libraries that let me parse a string accoring to some rules in all possible ways (like a tree) and pick the one that is most probable. I'm sure this exists, but it is hard to search for...

polm23 6y ago
> A side comment, for someone like me who isn't an NLP expert, it seems strange that there are no libraries that let me parse a string accoring to some rules in all possible ways (like a tree) and pick the one that is most probable. I'm sure this exists, but it is hard to search for... I think you're describing the Viterbi Algorithm.
pjc50 6y ago
Yes I'm slightly surprised that it doesn't use any of the tricks of parser interactive fiction or even SHRDLU.
PaulHoule 6y ago
It's a longstanding problem that a very large number of parse trees (1000s) can be found for sentences of any real complexity: there are so many of them that the one with the highest probability of being right is still likely to be wrong!
sweeneyrod 6y ago
Any natural language parser will let you get the most probable parse (for some definition of probable), some can also return a list of the n most probable parses. There are a few different types of parser implemented here https://nlp.stanford.edu/software/lex-parser.shtml https://nlp.stanford.edu/software/lex-parser.shtml

polm23 6y ago

> A side comment, for someone like me who isn't an NLP expert, it seems strange that there are no libraries that let me parse a string accoring to some rules in all possible ways (like a tree) and pick the one that is most probable. I'm sure this exists, but it is hard to search for... I think you're describing the Viterbi Algorithm.

pjc50 6y ago

Yes I'm slightly surprised that it doesn't use any of the tricks of parser interactive fiction or even SHRDLU.

PaulHoule 6y ago

It's a longstanding problem that a very large number of parse trees (1000s) can be found for sentences of any real complexity: there are so many of them that the one with the highest probability of being right is still likely to be wrong!

sweeneyrod 6y ago

Any natural language parser will let you get the most probable parse (for some definition of probable), some can also return a list of the n most probable parses. There are a few different types of parser implemented here https://nlp.stanford.edu/software/lex-parser.shtml https://nlp.stanford.edu/software/lex-parser.shtml