nltk/nltk — pull request #315 by kmike (2012-12-04 09:53:17+00:00)
Title: made parse.chart deterministic

nltk.parse.chart.Chart.parses is currently nondeterministic.

This causes random test failures in ccg.doctest (nltk.ccg.chart.CCGChartParser.nbest_parse may produce different output with the same input).

If I understand the issue correctly, Chart.child_pointer_lists returns dict keys:

```
return self._edge_to_cpls.get(edge, {}).keys()
```

The result is then used in Chart._trees method (which is called by Chart.trees method which is called by Chart.parses method). But dictionaries are unordered in Python and Chart.child_pointer_lists may return different results; this causes nondeterminism for other methods.

So in this pull request the result of Chart.child_pointer_lists is made deterministic (by using nltk.util.OrderedDict instead of dict). This affects parsing results (so tests are updated); ccg.doctest is always passes for me now.

parse.doctest becomes broken and it is not completely fixed with my commit:

```
======================================================================
FAIL: Doctest: parse.doctest
----------------------------------------------------------------------
Traceback (most recent call last):
File "/System/Library/Frameworks/Python.framework/Versions/2.7/lib/python2.7/doctest.py", line 2166, in runTest
raise self.failureException(self.format_failure(new.getvalue()))
AssertionError: Failed doctest test for parse.doctest
File "/Users/kmike/svn/nltk/nltk/test/parse.doctest", line 0

----------------------------------------------------------------------
File "/Users/kmike/svn/nltk/nltk/test/parse.doctest", line 834, in parse.doctest
Failed example:
unittest(isawjohn, "I saw John with a dog with my cookie", 5)
Expected nothing
Got:
Trees differ for parser: FeatureTopDownChartParser

```

Trees differ because the order of results become different for different parsers after this patch. I think they were the same by accident before, and the test should be fixed.

But I'm not expert in nltk.parse, I haven't used it myself, etc.; it'll be great if somebody with more knowledge will review this pull request because it affects parsing results.