commit bc2a67b0a5c3be54d027370fcccbb4583bc109d7
parent a49fbbf985126728f3c080f92294e5f260e706a0
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Sun, 12 Jun 2011 00:28:18 -0400
solution which uses too much ram, let's try paying cpu instead
Diffstat:
5 files changed, 87 insertions(+), 55 deletions(-)
diff --git a/buildtrie.py b/buildtrie.py
@@ -6,37 +6,66 @@ representing this mapping"""
import json
import sys
+NUM=4
+
# first item is a dictionnary from values to an int indicating the
# number of occurrences with this prefix having this value
# second item is a dictionnary from letters to descendent nodes
def empty_node():
- return [{}, {}]
+ return [0, {}]
+def empty_node2():
+ return [empty_node(), {}]
+
+trie = empty_node2()
-trie = empty_node()
+def too_ambiguous(trie):
+ values, children = trie
+ if values < 2:
+ return False
+ r = float(sum(sorted([x[0] for x in children.values()])[-NUM:])) / (values - 1)
+ return r < .99
-def insert(trie, key, val):
+def insert(trie, key):
"""Insert val for key in trie"""
values, children = trie
- # create a new value, if needed
- if val not in values.keys():
- values[val] = 0
# increment count for val
- values[val] += 1
+ trie[0] += 1
+ if trie[1] == None:
+ return
+ if too_ambiguous(trie):
+ trie[1] = None #too ambiguous
+ return
if len(key) > 0:
# create a new node if needed
if key[0] not in children.keys():
children[key[0]] = empty_node()
# recurse
- return insert(children[key[0]], key[1:], val)
+ return insert(children[key[0]], key[1:])
+
+def insert2(trie, key, val):
+ """Insert val for key in trie"""
+ values, children = trie
+ insert(values, val)
+ if len(key) > 0:
+ # create a new node if needed
+ if key[0] not in children.keys():
+ children[key[0]] = empty_node2()
+ # recurse
+ return insert2(children[key[0]], key[1:], val)
-for line in sys.stdin.readlines():
- line = line.split()
- value = line[0]
- word = line[1].lower() if len(line) == 2 else ''
+while True:
+ line = sys.stdin.readline()
+ if not line:
+ break
+ line = line.split('\t')
+ value = line[1].rstrip()[-4:][::-1]
+ word = line[0].lower()[-8:][::-1] if len(line) == 2 else ''
+ #print(word)
+ #print(value)
# a trailing space is used to mark termination of the word
# this is useful in cases where a prefix of a word is a complete,
# different word with a different value
- insert(trie, word+' ', value)
+ insert2(trie, word+' ', value)
print(json.dumps(trie))
diff --git a/compresstrie.py b/compresstrie.py
@@ -8,9 +8,20 @@ import sys
trie = json.load(sys.stdin)
+def linear(trie):
+ v, c = trie
+ if c == None:
+ return False
+ if len(c.keys()) == 0:
+ return True
+ elif len(c.keys()) > 1:
+ return False
+ else:
+ return linear(list(c.values())[0])
+
def compress(trie):
"""Compress the trie"""
- if len(trie[0].keys()) <= 1:
+ if linear(trie[0]):
# no need for children, there is no more doubt
trie[1] = {}
for child in trie[1].values():
diff --git a/haspirater.json b/haspirater.json
@@ -1 +0,0 @@
-["0", {"a": ["1", {"o": ["1", {}], " ": ["1", {}], "c": ["1", {}], "b": ["0", {"i": ["0", {}], "a": ["1", {}], "o": ["1", {}]}], "d": ["1", {"a": ["1", {}], "d": ["1", {}], "j": ["1", {}], "o": ["1", {"p": ["1", {"i": ["1", {" ": ["1", {}], "s": ["0", {}]}]}]}], "\u00ee": ["1", {}], "r": ["0", {}]}], "g": ["1", {}], "f": ["1", {}], "i": ["1", {}], "h": ["1", {}], "m": ["1", {}], "l": ["1", {"a": ["1", {}], "b": ["1", {}], "e": ["1", {" ": ["1", {}], "c": ["1", {}], "i": ["0", {}], "n": ["1", {}], "s": ["1", {}], "r": ["1", {}], "u": ["1", {}], "t": ["1", {}], "z": ["1", {}]}], "d": ["1", {}], "i": ["1", {"b": ["1", {}], "o": ["0", {}]}], "\u00e8": ["1", {"r": ["1", {}], "t": ["1", {}], "n": ["0", {}]}], "l": ["1", {"a": ["1", {"l": ["0", {}], "g": ["1", {}]}], " ": ["1", {}], "e": ["1", {}], "i": ["1", {}], "s": ["1", {}], "u": ["0", {}]}], "o": ["1", {}], "\u00e9": ["1", {}], "s": ["1", {}], "t": ["1", {}]}], "\u00ef": ["1", {}], "n": ["1", {}], "q": ["1", {}], "p": ["1", {}], "s": ["1", {}], "r": ["1", {"a": ["1", {}], "c": ["1", {}], "e": ["1", {}], "d": ["1", {}], "g": ["1", {}], "f": ["1", {}], "i": ["1", {}], "k": ["1", {}], "m": ["0", {}], "l": ["1", {}], "o": ["1", {}], "n": ["1", {}], "p": ["1", {}], "r": ["1", {}], "t": ["1", {}], "v": ["1", {}]}], "u": ["1", {}], "t": ["1", {}], "v": ["0", {"a": ["1", {}], "e": ["0", {" ": ["1", {}], "l": ["0", {"a": ["0", {}], "\u00e2": ["0", {}], "e": ["0", {"r": ["1", {" ": ["1", {}]}], "z": ["0", {}]}], "\u00e9": ["0", {" ": ["0", {}], "s": ["0", {}], "e": ["0", {" ": ["1", {}], "s": ["0", {}]}]}], "\u00e8": ["0", {}], "l": ["0", {}], "o": ["0", {}], "i": ["0", {}]}], "n": ["1", {}], "s": ["1", {}], "r": ["1", {}], "u": ["1", {}]}], "i": ["1", {}], "\u00e8": ["0", {}], "r": ["1", {}], "u": ["1", {}]}], "y": ["1", {}], "\u00ff": ["0", {}]}], " ": ["1", {}], "\u00e2": ["1", {}], "e": ["0", {"a": ["1", {"r": ["1", {}], "u": ["1", {"m": ["1", {}], "t": ["0", {}]}]}], "i": ["1", {}], "m": ["1", {}], "l": ["0", {"l": ["0", {"\u00e9": ["0", {}], "e": ["1", {"s": ["0", {}], "b": ["1", {}]}], "o": ["1", {}]}], "v": ["0", {}]}], "n": ["1", {}], "p": ["1", {}], "s": ["1", {}], "r": ["0", {"c": ["1", {"h": ["1", {}], "u": ["0", {}]}], "b": ["0", {}], "m": ["0", {"\u00e9": ["0", {}], "i": ["0", {"t": ["1", {"a": ["0", {}], "i": ["1", {}]}], "n": ["0", {}]}]}], "n": ["1", {}], "p": ["1", {}], "s": ["1", {}], "t": ["1", {}]}], "u": ["0", {"s": ["1", {}], "r": ["0", {" ": ["0", {}], "e": ["0", {}], "t": ["1", {}]}], "l": ["1", {}], "/": ["1", {}]}], "t": ["1", {}], "x": ["0", {}]}], "i": ["0", {"a": ["1", {"t": ["1", {"a": ["1", {}], "u": ["0", {}]}]}], " ": ["1", {}], "c": ["1", {}], "b": ["0", {"e": ["0", {}], "o": ["1", {}]}], "e": ["1", {" ": ["1", {}], "r": ["0", {" ": ["0", {}]}], "m": ["1", {}]}], "d": ["1", {}], "g": ["1", {}], "f": ["1", {}], "\u00e9": ["1", {}], "h": ["1", {}], "l": ["1", {"a": ["0", {"i": ["1", {}], "r": ["0", {}]}], "b": ["1", {}], "e": ["1", {}], "d": ["1", {"e": ["1", {"s": ["0", {}], "g": ["1", {}]}]}], "o": ["1", {}]}], "n": ["1", {" ": ["1", {}], "s": ["1", {}], "d": ["1", {"i": ["1", {}], "o": ["0", {}]}]}], "p": ["0", {"p": ["0", {"i": ["1", {}], "o": ["0", {}]}], "h": ["1", {}], " ": ["1", {}]}], "s": ["0", {"s": ["1", {}], "t": ["0", {}]}], "r": ["1", {"a": ["1", {}], "o": ["1", {"s": ["1", {}], "n": ["0", {}]}]}], "t": ["1", {}], "v": ["0", {}]}], "\u00e8": ["1", {"r": ["1", {}], "b": ["0", {}], "l": ["1", {}]}], "\u00ea": ["1", {}], "l": ["1", {}], "o": ["0", {" ": ["1", {}], "c": ["1", {}], "b": ["1", {}], "d": ["1", {}], "g": ["1", {}], "f": ["0", {}], "h": ["1", {}], "m": ["0", {"a": ["1", {}], " ": ["1", {}], "e": ["1", {}], "\u00e9": ["0", {}], "m": ["0", {}], "o": ["0", {}], "i": ["0", {}]}], "l": ["1", {"\u00e0": ["1", {}], "l": ["1", {}], "o": ["0", {}], "d": ["1", {}]}], "o": ["1", {}], "n": ["0", {" ": ["1", {}], "d": ["1", {}], "g": ["1", {}], "o": ["0", {}], "n": ["0", {"i": ["1", {}], "\u00ea": ["0", {}], "e": ["0", {}]}], "s": ["1", {}], "t": ["1", {}]}], "q": ["1", {}], "p": ["1", {}], "s": ["0", {"a": ["1", {}], "p": ["0", {}], "t": ["0", {}]}], "r": ["0", {"a": ["0", {}], "d": ["1", {}], "i": ["0", {"z": ["0", {}], "o": ["1", {}]}], "m": ["1", {"i": ["1", {}], "o": ["0", {}]}], "l": ["0", {}], "n": ["1", {}], "s": ["1", {}], "r": ["0", {}]}], "u": ["1", {}], "t": ["1", {}], "w": ["1", {}], "y": ["1", {}]}], "\u00e9": ["0", {"b": ["0", {"\u00e9": ["0", {" ": ["0", {}], "c": ["1", {}], "t": ["0", {}]}], "\u00e8": ["0", {}], "r": ["0", {}], "e": ["0", {}]}], "m": ["0", {}], "l": ["0", {"i": ["0", {"p": ["1", {}], "c": ["0", {}], "o": ["0", {}]}], "a": ["1", {"i": ["1", {}], " ": ["1", {}], "s": ["0", {}], "n": ["1", {}]}], "e": ["1", {}], "\u00e9": ["1", {}], "\u00e8": ["1", {}]}], "q": ["1", {}], "s": ["0", {}], "r": ["1", {"i": ["0", {"s": ["1", {}], "t": ["0", {}]}], "\u00e9": ["0", {}], "a": ["1", {}], "o": ["1", {"s": ["1", {}], "u": ["1", {}], "\u00ef": ["0", {}], "n": ["1", {}]}]}], "t": ["0", {}]}], "\u00e1": ["1", {}], "u": ["1", {"n": ["1", {}], "\u00e9": ["1", {}], "\u00e2": ["1", {}], "a": ["1", {}], "c": ["1", {}], "b": ["1", {}], "e": ["1", {}], "d": ["0", {}], "g": ["1", {}], "i": ["1", {"e": ["1", {}], "l": ["0", {}], "o": ["1", {}], "s": ["0", {}], "r": ["1", {}], "t": ["1", {}]}], "\u00e8": ["1", {}], "m": ["0", {"a": ["0", {"i": ["0", {" ": ["1", {}], "s": ["1", {}], "e": ["1", {}], "t": ["1", {}], "n": ["0", {}]}], " ": ["1", {}], "g": ["1", {}], "n": ["0", {"i": ["0", {}], "t": ["1", {}]}]}], " ": ["1", {}], "b": ["0", {"l": ["0", {"e": ["0", {" ": ["0", {}], "s": ["1", {" ": ["1", {}]}]}]}], "o": ["1", {}]}], "e": ["0", {" ": ["1", {}], "c": ["0", {}], "m": ["1", {}], "n": ["1", {}], "r": ["1", {}], "u": ["0", {"x": ["1", {}], "r": ["0", {}]}], "z": ["1", {}]}], "i": ["0", {"f": ["0", {}], "l": ["0", {}], "o": ["1", {}], "d": ["0", {}]}], "\u00e9": ["1", {}], "\u00e8": ["1", {}], "o": ["1", {}], "p": ["1", {}], "u": ["0", {}]}], "l": ["1", {}], "o": ["1", {}], "\u00ee": ["0", {}], "q": ["1", {}], "p": ["1", {}], "s": ["1", {}], "r": ["1", {}], "t": ["1", {}], "h": ["1", {}], "z": ["1", {}]}], "\u00f4": ["0", {"p": ["0", {}], "t": ["0", {}], "l": ["1", {}]}], "y": ["0", {"a": ["1", {}], "d": ["0", {}], "g": ["0", {}], "\u00e8": ["0", {}], "m": ["0", {}], "p": ["0", {}], "s": ["0", {}], "r": ["0", {}]}]}]
diff --git a/haspirater.py b/haspirater.py
@@ -1,40 +0,0 @@
-#!/usr/bin/python3
-
-"""Determine if a French word starts by an aspirated 'h' or not, by a
-lookup in a precompiled trie"""
-
-import os
-import json
-import sys
-
-f = open(os.path.join(os.path.dirname(
- os.path.realpath(__file__)), 'haspirater.json'))
-trie = json.load(f)
-f.close()
-
-def do_lookup(trie, key):
- if len(key) == 0 or (key[0] not in trie[1].keys()):
- return trie[0]
- return do_lookup(trie[1][key[0]], key[1:])
-
-def lookup(key):
- """Return True iff key starts with an aspirated 'h'"""
- if key == '' or key[0] != 'h':
- raise ValueError
- return do_lookup(trie, key[1:] + ' ') == '1'
-
-if __name__ == '__main__':
- while True:
- line = sys.stdin.readline()
- if not line:
- break
- line = line.lower().lstrip().rstrip()
- try:
- result = lookup(line)
- if result:
- print("%s: aspirated" % line)
- else:
- print("%s: not aspirated" % line)
- except ValueError:
- print("%s: no leading 'h'" % line)
-
diff --git a/pron.py b/pron.py
@@ -0,0 +1,33 @@
+#!/usr/bin/python3
+
+"""Determine if a French word starts by an aspirated 'h' or not, by a
+lookup in a precompiled trie"""
+
+import os
+import json
+import sys
+from pprint import pprint
+
+f = open(os.path.join(os.path.dirname(
+ os.path.realpath(__file__)), 'data.json'))
+trie = json.load(f)
+f.close()
+
+def do_lookup(trie, key):
+ if len(key) == 0 or (key[0] not in trie[1].keys()):
+ print(key)
+ return trie[0]
+ return do_lookup(trie[1][key[0]], key[1:])
+
+def lookup(key):
+ """Return pronunciations for key"""
+ return do_lookup(trie, key[::-1] + ' ')
+
+if __name__ == '__main__':
+ while True:
+ line = sys.stdin.readline()
+ if not line:
+ break
+ line = line.lower().lstrip().rstrip()
+ pprint(lookup(line))
+
