Merging and splitting a word list of synonyms
(I'm trying to update the hunspell spelling dictionary) My synonyms file looks something like this:
mylist="""
specimen|3
sample
prototype
example
sample|3
prototype
example
specimen
prototype|3
example
specimen
sample
example|3
specimen
sample
prototype
protoype|1
illustration
"""
The first step is to combine the repeating words. In the example above, the word "prototype" is repeated. So I will need to merge it together. The score will go from 3 to 4 because the synonym for "illustration" has been added.
specimen|3
sample
prototype
example
sample|3
prototype
example
specimen
prototype|4
example
specimen
sample
illustration
example|3
specimen
sample
prototype
The second step is more difficult. It is not enough to combine duplicates. The added word must also be reflected in the associated words. In this case, I need to search for "prototype" in the synonym list, and if found, the word "illustration" should be added. The final wordlist will look like this:
specimen|4
sample
prototype
example
illustration
sample|4
prototype
example
specimen
illustration
prototype|4
example
specimen
sample
illustration
example|4
specimen
sample
prototype
illustration
The new word "illustration" must be added to the original list with all 4 associated words.
illustration|4
example
specimen
sample
prototype
What I have tried:
myfile=StringIO.StringIO(mylist)
for lineno, i in enumerate(myfile):
if i:
try:
if int(i.split("|")[1]) > 0:
print lineno, i.split("|")[0], int(i.split("|")[1])
except:
pass
The above code returns a word with line numbers and a count.
1 specimen 3
5 sample 3
9 prototype 3
13 example 3
17 protoype 1
This means I need to concatenate 1 word on line 18 with the word found on line 9 ("prototype") at 4th position. If I can do this, I will complete step 1 of the task.
source to share
The problem you described is the classic Union-Find problem, which can be solved using the disjoint set algorithm. Don't reinvent the wheel.
Read about Union-Find / Disjoint set:
http://en.wikipedia.org/wiki/Disjoint-set_data_structure
Or questions:
Connection Set Search Algorithm
Union find implementation using Python
class DisjointSet(object):
def __init__(self):
self.leader = {} # maps a member to the group leader
self.group = {} # maps a group leader to the group (which is a set)
def add(self, a, b):
leadera = self.leader.get(a)
leaderb = self.leader.get(b)
if leadera is not None:
if leaderb is not None:
if leadera == leaderb: return # nothing to do
groupa = self.group[leadera]
groupb = self.group[leaderb]
if len(groupa) < len(groupb):
a, leadera, groupa, b, leaderb, groupb = b, leaderb, groupb, a, leadera, groupa
groupa |= groupb
del self.group[leaderb]
for k in groupb:
self.leader[k] = leadera
else:
self.group[leadera].add(b)
self.leader[b] = leadera
else:
if leaderb is not None:
self.group[leaderb].add(a)
self.leader[a] = leaderb
else:
self.leader[a] = self.leader[b] = a
self.group[a] = set([a, b])
mylist="""
specimen|3
sample
prototype
example
sample|3
prototype
example
specimen
prototype|3
example
specimen
sample
example|3
specimen
sample
prototype
prototype|1
illustration
specimen|1
cat
happy|2
glad
cheerful
"""
ds = DisjointSet()
for line in mylist.strip().splitlines():
if '|' in line:
node, _ = line.split('|')
else:
ds.add(node, line)
for _,g in ds.group.items():
print g
>>>
set(['specimen', 'illustration', 'cat', 'sample', 'prototype', 'example'])
set(['cheerful', 'glad', 'happy'])
Using dijkstra's algorithm might solve the problem, but I think it is overkill since you don't really need the shortest distance between nodes, you just need related components in the graph.
source to share
Use a graph for this:
mylist="""
specimen|3
sample
prototype
example
sample|3
prototype
example
specimen
prototype|3
example
specimen
sample
example|3
specimen
sample
prototype
prototype|1
illustration
specimen|1
cat
happy|2
glad
cheerful
"""
import networkx as nx
G = nx.Graph()
nodes = []
for line in mylist.strip().splitlines():
if '|' in line:
node, _ = line.split('|')
if node not in nodes:
nodes.append(node)
G.add_node(node)
else:
G.add_edge(node, line)
if line not in nodes:
nodes.append(line)
for node in nodes:
neighbors = G.neighbors(node)
non_neighbors = []
for non_nb in nx.non_neighbors(G, node):
try:
if nx.bidirectional_dijkstra(G, node, non_nb):
non_neighbors.append(non_nb)
except Exception:
pass
syns = neighbors + non_neighbors
print '{}|{}'.format(node, len(syns))
print '\n'.join(syns)
Output:
specimen|5
sample
prototype
example
cat
illustration
sample|5
specimen
prototype
example
illustration
cat
prototype|5
sample
specimen
example
illustration
cat
example|5
sample
specimen
prototype
illustration
cat
illustration|5
prototype
specimen
cat
sample
example
cat|5
specimen
illustration
sample
prototype
example
happy|2
cheerful
glad
glad|2
happy
cheerful
cheerful|2
happy
glad
The graph will look like this:
source to share