Link Grammar Parser - Patched Version
-------------------------------------
Version 4.3.5
This directory contains a *patched* version of the final original
release of the Link Grammar Parser. It has been patched to fix a
few bugs, add a few enhancements, and, in general, make the Link
Grammar Parser easier to use. This version includes Java bindings.
It is released under the BSD license (which is GPL compatible),
making it freely available for private and commercial use, with
few restrictions. The terms of the license are given in the
LICENSE file included with this software, and also available at
http://www.link.cs.cmu.edu/link/license.html.
Please see the web page http://www.abisource.com/projects/link-grammar/
for more information. The original website, including documentation,
is located at http://www.link.cs.cmu.edu/link
CONTENTS of this directory:
LICENSE The license describing terms of use
link-grammar/*.c The program. (Written in ANSI-C)
data/en/4.0.dict The file containing the dictionary definitions.
data/en/4.0.knowledge The post-processing knowledge file.
data/en/4.0.constituents The constituent knowledge file.
data/en/4.0.affix The affix file.
data/en/tiny.dict A small sample dictionary.
data/en/words/* A directory full of word lists.
data/en/4.0.batch This is a batch file of sentences (both grammatical
and ungrammatical ones) that are handled correctly
by this release of the system. Feed this into the
parser with "./link-parser < 4.0.batch"
configure The GNU configuration script
UNPACKING and signature verification:
The system is distributed using the normal tar.gz format; it can be
extracted using the "tar -zxf link-grammar.tar.gz" command at the
command line.
The files have been digitally signed to make sure that there was no
corruption of the dataset during download, and to help ensure that
no malicious changes were made to the code internals by third
parties. The signatures can be checked with the gpg command:
gpg --verify link-grammar-4.3.5.tar.gz.asc
which should generate output identical to (except for the date):
gpg: Signature made Tue Feb 26 19:41:07 2008 CST using RSA key ID C0389241
gpg: Good signature from "Linas Vepstas (current active email; others are inactive) <linasvepstas@gmail.com>"
Alternately, the md5 checksums can be verified. These do not provide
cryptographic security, but they can detect simple corruption. To
verify the checksums, issue "md5sum -c MD5SUM" at the command line.
CREATING the system:
To compile the link-grammar shared library and demonstration program,
at the command line, type:
./configure
make
To install, change user to "root" and say
make install
This will install the lib-link-grammar.so library into /usr/local/lib
the header files in /usr/local/include/link-grammar
and the dictionaries into /usr/local/share/link-grammar.
The /usr/local install target can be over-ridden using the
standard GNU configure --prefix option, so for example:
./configure --prefix=/opt/link-grammar
By using pkg-config (see below), non-standard install locations
can be automatically detected.
The system has been tested and works well on 32 and 64-bit Linux
systems, as well as on many Microsoft Windows systems, under the
CYGWIN development environment.
Windows users may need to also do the following:
gcc -shared -Wall -D_JNI_IMPLEMENTATION_ -Wl,--kill-at .libs/analyze-linkage.o .libs/and.o .libs/api.o .libs/build-disjuncts.o
.libs/command-line.o .libs/constituents.o .libs/count.o .libs/error.o .libs/extract-links.o .libs/fast-match.o .libs/idiom.o
.libs/linkset.o .libs/massage.o .libs/post-process.o .libs/pp_knowledge.o .libs/pp_lexer.o .libs/pp_linkset.o .libs/preparation.o
.libs/print.o .libs/print-util.o .libs/prune.o .libs/read-dict.o .libs/resources.o .libs/string-set.o .libs/tokenize.o
.libs/utilities.o .libs/word-file.o .libs/word-utils.o .libs/prefix.o -o /usr/local/bin/link-grammar.dll
gcc -shared -Wall -D_JNI_IMPLEMENTATION_ -Wl,--kill-at .libs/jni-client.o /usr/local/bin/link-grammar.dll -o
/usr/local/bin/link-grammar-java.dll
RUNNING the program:
To run the program issue the Unix command:
./link-parser
This starts the program. Help is available there with "!help". A
number of user-settable variables control what happens. "!var" shows
these variables and their current values.
The program can run in batch mode for testing the system on a large
number of sentences. The following command runs the parser on
a file called 4.0.batch
./link-parser < 4.0.batch
The line "!batch" near the top of 4.0.batch turns on batch mode. In
this mode sentences labeled with an initial "*" should be rejected
and those not starting with a "*" should be accepted. Any deviation
from this behavior is reported as an error.
USING the parser in your own applications:
There is a API (application program interface) to the parser. This
makes it easy to incorporate it into your own applications. The API
documented on the web site.
USING pkg-config:
To make compiling and linking easier, the current release uses
the pkg-config system. To determine the location of the link-grammar
header files, say `pkg-config --cflags link-grammar` To obtain
the location of the libraries, say `pkg-config --libs link-grammar`
Thus, for example, a typical makefile might include the targets:
.c.o:
cc -O2 -g -Wall -c $< `pkg-config --cflags link-grammar`
$(EXE): $(OBJS)
cc -g -o $@ $^ `pkg-config --libs link-grammar`
JAVA bindings:
This release includes a very simple Java binding. Its use is optional.
It can be accessed by copying the file LinkGrammar.java into your java
project. Alternately, "ant" can be used, with the build.xml file, to
build the appropriate jar file.
The bindings will be built automatically if jni.h can be found.
Some common java JVM distributions (most notably, the ones from Sun)
place this file in unusual locations, where it cannot be found.
To remedy this, specify the location with the CPPFLAGS variable:
so, for example,
export CPPFLAGS="-I/opt/jdk1.5/include/:/opt/jdk1.5/include/linux"
or
export CPPFLAGS="-I/c/java/jdk1.6.0/include/ -I/c/java/jdk1.6.0/include/win32/"
Please note that the use of /opt is non-standard, and most system
tools will fail to find packages installed there.
COMMERCIAL use:
The original authors would be pleased to discuss alternate
licensing terms and/or additional research work, with those
wanting to use this system under a paid contract.
Academic products or papers should reference the various
link grammar publications.
ADDRESSES
If you have any questions, or find any bugs, please feel free
to send a note to the mailing list:
link-grammar@googlegroups.com
Although all messages should go to the mailing list, the current
maintainers can be contacted at:
Dom Lachowicz - <domlachowicz@gmail.com>
Linas Vepstas - <linasvepstas@gmail.com>
The original authors of the Link Grammar parser are:
Daniel Sleator sleator@cs.cmu.edu
Computer Science Department 412-268-7563
Carnegie Mellon University www.cs.cmu.edu/~sleator
Pittsburgh, PA 15213
Davy Temperley dtemp@theory.esm.rochester.edu
Eastman School of Music 716-274-1557
26 Gibbs St. www.link.cs.cmu.edu/temperley
Rochester, NY 14604
John Lafferty lafferty@cs.cmu.edu
Computer Science Department 412-268-6791
Carnegie Mellon University www.cs.cmu.edu/~lafferty
Pittsburgh, PA 15213
TODO:
Some working notes.
read-dict.c: after running insert_dict() to create dictionary tree,
the tree is highly unbalanced, and should be rebalanced before use.
This would provide a minor performance improvement.
tokenize.c: build_sentence_expressions() contains some
English-language-specific morphology guessing. This should be
refactored out, as it doesn't really apply to non-English
languages.
no-links-cross: Link Grammar uses a constraint that al linakges must
be planar graphs. While this is mostly correct, it would probably
be more correct to use "landmark transitivity" as articulated by
Hudson in the Word Grammar theory. This might allow the elimination
of most or all post-processing rules.
This is done by making each link directional: one end of the link
is the parent. (e.g. noun, noun-modifier: the noun is the parent).
Parents are landmarks for children. Transitivity is applied to
parent-child relationships. Specifically, the no-links-cross
rule is replaced by two landmark transitivity rules:
-- If B is a landmark for C, then A is also a type-L landmark for C
-- If A is a landmark for C, then B is also a landmark for C
where type-L means either a right-going or left-going link.
See http://goertzel.org/ProwlGrammar.pdf for details.
"to be fishing": Link grammar offers four parses of "I was fishing for
evidence", two of which are given low scores, and two are given
high scores. Of the two with high scores, one parse is clearly bad.
Its links "to be fishing.noun" as opposed to the correct
"to be fishing.gerund". That is, I can be happy, healthy and wise,
but I certainly cannot be fishing.noun. This is perhaps not
just a bug in the structure of the dictionary, but is perhaps
deeper: link-grammar has little or no concept of lexical units
(i.e. collocations, idioms, institutional phrases), which thus
allows parses with bad word-senses to sneak in.
The goal is to introduce more knowledge of lexical units into LG.
incremental parsing: to avoid a combinatorial explosion of parses,
it would be nice to have an incremental parsing, phrase by phrase,
using a Viterbi-like algorithm to obtain the parse. Thus, for example,
the parse of the last half of a long, run-on sentence should not be
sensitive to the parse of the begining of the sentence.
Doing so would help with combinatorial explosion. So, for example,
if the first half of a sentence has 4 plausible parses, and the
last half has 4 more, then link-grammar reports 16 parses total.
It would be much, much more useful to instead be given the
factored results: i.e. the for plausbile parses for the
first half, and the four plausible parses for the last half.
The lower combinatoric stress would ease the burden on
downstream users of link-grammar.
(This somewhat resembles the application of construction grammar
ideas to the link-grammar dictionary).
