Chart Parsing
Clearly these are very different sentences—the first is a
question, and the second is an instruction. In spite of this, the first
threewords of each sentence are the same.
When a parser is examining one of these sentences, it is quite
likely to have to backtrack to the beginning if it makes the wrong choice in
the first case for the structure of the sentence. In longer sentences, this can
be a much greater problem, particularly as it involves examining the same words
more than once, without using the fact that the words have already been
analyzed.
Another
method that is sometimes used for parsing natural language is chart parsing.
In the
worst case, chart parsing will parse a sentence of n words in O(n3) time. In
many cases it will perform better than this and will parse most sentences in
O(n2) or even O(n) time.
In
examining sentence 1 above, the chart parser would note that the words two
children form a noun phrase. It would note this on its first pass through the
sentence and would store this information in a chart, meaning it would not need
to examine those words again on a subsequent pass, after backtracking.
The
initial chart for the sentence The cat eats a big fish is shown in Fig 10.3 It
shows the chart that the chart parse algorithm would start with for parsing the
sentence.
The chart
consists of seven vertices, which will become connected to each other by edges.
The edges will show how the constituents of the sentence combine together.
The chart
parser starts by adding the following edge to the chart:
[0, 0,
Target→• Sentence]
This
notation means that the edge connects vertex 0 to itself (the first two numbers
in the square brackets show which vertices the edge connects).
Target is
the target that we want to find, which is really just a placeholder to enable
us to have an edge that requires us to find a whole sentence. The arrow
indicates that in order to make what is on its left-hand side (Target) we need
to find what is on its right-hand side (Sentence). The dot (•) shows
what has
been found already, on its left-hand side, and what is yet to be found, on its
right-hand side. This is perhaps best explained by examining an example.
Consider
the following edge, which is shown in the chart in Figure 10.4: [0, 2,
Sentence→NounPhrase • VerbPhrase]
This
means that an edge exists connecting nodes 0 and 2. The dot shows us that we
have already found a NounPhrase (the cat) and that we are looking for a
VerbPhrase.
Once we
have found the VerbPhrase, we will have what is on the left-hand side of the
arrow—that is, a Sentence.
The chart
parser can add edges to the chart using the following three rules:
If we
have an edge [x, y, A → B • C], which needs to find a C, then an edge can be
added that supplies that C (i.e., the edge [x, y, C→ •
E]),
where E is some sequence of terminals or nonterminals which
can be
replaced by a C).
If we
have two edges, [x, y, A → B • C D] and [y, z, C → E •}, then these two edges
can be combined together to form a new edge:
[x, z,
A→B C • D].
Related Topics
Privacy Policy, Terms and Conditions, DMCA Policy and Compliant
Copyright © 2018-2023 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.