Parsing city of origin and destination city from a string

Re:Parsing city of origin and destination city from a string by captainmuon on Monday July 06, 2020 @07:28AM (#23746751)

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...

[ Parent | on HN ]

Re:Parsing city of origin and destination city from a string by polm23 on Monday July 06, 2020 @07:34AM (#23746788)

> 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.

[ Parent | on HN ]

Re:Parsing city of origin and destination city from a string by PaulHoule on Monday July 06, 2020 @12:15PM (#23749382)

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!

[ Parent | on HN ]

Re:Parsing city of origin and destination city from a string by sweeneyrod on Tuesday July 07, 2020 @05:35AM (#23757308)

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

[ Parent | on HN ]

Re:Parsing city of origin and destination city from a string by pjc50 on Monday July 06, 2020 @07:37AM (#23746807)

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

[ Parent | on HN ]