commit 322770b960f1fc53d85876c51b0f8728d4f7250f
parent f677bf008e5d1f4275f3ed8ab7d22b1d8ee63ecf
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Sat, 11 Jun 2011 21:14:46 -0400
prune useless nodes in majoritytrie.py (thanks robin)
Diffstat:
5 files changed, 32 insertions(+), 12 deletions(-)
diff --git a/README b/README
@@ -98,11 +98,13 @@ needed.
Instead of the list of values with their counts, nodes are relabeled to
carry the most common value. This step could be skipped to keep
-confidence values.
+confidence values. We also drop useless leaf nodes there.
== 5. Additionnal stuff ==
You can use trie2dot.py to convert the output of buildtrie.py or
compresstrie.py in the dot format which can be used to render a drawing
-of the trie. The result of such a drawing is given as aspirated_h.pdf
+of the trie. The result of such a drawing is given as haspirater.pdf
+(before majoritytrie.py: contains frequency info, but more nodes)
+and haspirater_majority.pdf (no frequency, less nodes).
diff --git a/haspirater.json b/haspirater.json
@@ -1 +1 @@
-["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", {}]}]}]
+["0", {"a": ["1", {"b": ["0", {"a": ["1", {}], "o": ["1", {}]}], "d": ["1", {"o": ["1", {"p": ["1", {"i": ["1", {"s": ["0", {}]}]}]}], "r": ["0", {}]}], "l": ["1", {"e": ["1", {"i": ["0", {}]}], "i": ["1", {"o": ["0", {}]}], "\u00e8": ["1", {"n": ["0", {}]}], "l": ["1", {"a": ["1", {"l": ["0", {}]}], "u": ["0", {}]}]}], "r": ["1", {"m": ["0", {}]}], "v": ["0", {"a": ["1", {}], "e": ["0", {" ": ["1", {}], "l": ["0", {"e": ["0", {"r": ["1", {}]}], "\u00e9": ["0", {"e": ["0", {" ": ["1", {}]}]}]}], "n": ["1", {}], "s": ["1", {}], "r": ["1", {}], "u": ["1", {}]}], "i": ["1", {}], "r": ["1", {}], "u": ["1", {}]}], "\u00ff": ["0", {}]}], " ": ["1", {}], "\u00e2": ["1", {}], "e": ["0", {"a": ["1", {"u": ["1", {"t": ["0", {}]}]}], "i": ["1", {}], "m": ["1", {}], "l": ["0", {"l": ["0", {"e": ["1", {"s": ["0", {}]}], "o": ["1", {}]}]}], "n": ["1", {}], "p": ["1", {}], "s": ["1", {}], "r": ["0", {"c": ["1", {"u": ["0", {}]}], "m": ["0", {"i": ["0", {"t": ["1", {"a": ["0", {}]}]}]}], "n": ["1", {}], "p": ["1", {}], "s": ["1", {}], "t": ["1", {}]}], "u": ["0", {"s": ["1", {}], "r": ["0", {"t": ["1", {}]}], "l": ["1", {}], "/": ["1", {}]}], "t": ["1", {}]}], "i": ["0", {"a": ["1", {"t": ["1", {"u": ["0", {}]}]}], " ": ["1", {}], "c": ["1", {}], "b": ["0", {"o": ["1", {}]}], "e": ["1", {"r": ["0", {}]}], "d": ["1", {}], "g": ["1", {}], "f": ["1", {}], "\u00e9": ["1", {}], "h": ["1", {}], "l": ["1", {"a": ["0", {"i": ["1", {}]}], "d": ["1", {"e": ["1", {"s": ["0", {}]}]}]}], "n": ["1", {"d": ["1", {"o": ["0", {}]}]}], "p": ["0", {"p": ["0", {"i": ["1", {}]}], "h": ["1", {}], " ": ["1", {}]}], "s": ["0", {"s": ["1", {}]}], "r": ["1", {"o": ["1", {"n": ["0", {}]}]}], "t": ["1", {}]}], "\u00e8": ["1", {"b": ["0", {}]}], "\u00ea": ["1", {}], "l": ["1", {}], "o": ["0", {" ": ["1", {}], "c": ["1", {}], "b": ["1", {}], "d": ["1", {}], "g": ["1", {}], "h": ["1", {}], "m": ["0", {"a": ["1", {}], " ": ["1", {}], "e": ["1", {}]}], "l": ["1", {"o": ["0", {}]}], "o": ["1", {}], "n": ["0", {" ": ["1", {}], "d": ["1", {}], "g": ["1", {}], "n": ["0", {"i": ["1", {}]}], "s": ["1", {}], "t": ["1", {}]}], "q": ["1", {}], "p": ["1", {}], "s": ["0", {"a": ["1", {}]}], "r": ["0", {"d": ["1", {}], "i": ["0", {"o": ["1", {}]}], "m": ["1", {"o": ["0", {}]}], "n": ["1", {}], "s": ["1", {}]}], "u": ["1", {}], "t": ["1", {}], "w": ["1", {}], "y": ["1", {}]}], "\u00e9": ["0", {"b": ["0", {"\u00e9": ["0", {"c": ["1", {}]}]}], "l": ["0", {"i": ["0", {"p": ["1", {}]}], "a": ["1", {"s": ["0", {}]}], "e": ["1", {}], "\u00e9": ["1", {}], "\u00e8": ["1", {}]}], "q": ["1", {}], "r": ["1", {"i": ["0", {"s": ["1", {}]}], "\u00e9": ["0", {}], "o": ["1", {"\u00ef": ["0", {}]}]}]}], "\u00e1": ["1", {}], "u": ["1", {"d": ["0", {}], "i": ["1", {"l": ["0", {}], "s": ["0", {}]}], "m": ["0", {"a": ["0", {"i": ["0", {" ": ["1", {}], "s": ["1", {}], "e": ["1", {}], "t": ["1", {}]}], " ": ["1", {}], "g": ["1", {}], "n": ["0", {"t": ["1", {}]}]}], " ": ["1", {}], "b": ["0", {"l": ["0", {"e": ["0", {"s": ["1", {}]}]}], "o": ["1", {}]}], "e": ["0", {" ": ["1", {}], "m": ["1", {}], "n": ["1", {}], "r": ["1", {}], "u": ["0", {"x": ["1", {}]}], "z": ["1", {}]}], "i": ["0", {"o": ["1", {}]}], "\u00e9": ["1", {}], "\u00e8": ["1", {}], "o": ["1", {}], "p": ["1", {}]}], "\u00ee": ["0", {}]}], "\u00f4": ["0", {"l": ["1", {}]}], "y": ["0", {"a": ["1", {}]}]}]
diff --git a/haspirater_majority.pdf b/haspirater_majority.pdf
Binary files differ.
diff --git a/majoritytrie.py b/majoritytrie.py
@@ -1,7 +1,7 @@
#!/usr/bin/env python3
-"""Read json trie in stdin, keep majority value at each node and output
-trie to stdout"""
+"""Read json trie in stdin, keep majority value at each node, remove
+useless leaf nodes and output trie to stdout"""
import json
import sys
@@ -15,8 +15,14 @@ def get_majority(d):
def majority(trie):
"""Keep only the most probable value at each node"""
trie[0] = get_majority(trie[0])
- for child in trie[1].values():
- majority(child)
+ useless = []
+ for child in trie[1].keys():
+ majority(trie[1][child])
+ # if it is relabeled to our majority value and is a leaf, drop it
+ if trie[1][child][0] == trie[0] and trie[1][child][1] == {}:
+ useless.append(child)
+ for child in useless:
+ del(trie[1][child])
majority(trie)
diff --git a/trie2dot.py b/trie2dot.py
@@ -12,10 +12,18 @@ trie = json.load(sys.stdin)
free_id = 0
def cget(d, k):
- if k in d.keys():
- return d[k]
- else:
- return 0
+ try:
+ if k in d.keys():
+ return d[k]
+ else:
+ return 0
+ except AttributeError:
+ # we have only one value, not a dictionary
+ # this happens after majoritytrie.py
+ if k == d:
+ return 1
+ else:
+ return 0
def int2strbyte(i):
s = hex(i).split('x')[1]
@@ -30,7 +38,11 @@ def fraction2rgb(fraction):
def total(x):
key, node = x
- return sum(node[0].values())
+ try:
+ return sum(node[0].values())
+ except AttributeError:
+ # we have only one value, not a dictionary
+ return 1
def to_dot(trie, prefix=''):
global free_id
