merge and split synonym word list

Question

(I am trying to update hunspell spelling dictionary) My synonym 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 merge duplicate words. In the example mentioned above, the word "prototype" is repeated. So I will need to club it together. The count will change from 3 to 4 because the "illustration" synonym is 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 complicated. It is not enough to merge duplicates. The added word should also be reflected to the linked words. In this case I need to search for "prototype" in synonym list and if found, the "illustration" word should get added. The final list of words 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

A new word "illustration" should get added to the original list with all 4 linked 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 word with line numbers and count.

1 specimen 3
5 sample 3
9 prototype 3
13 example 3
17 protoype 1

It means I need to merge 1 word on line number 18 with the word found on line number 9 ("prototype") at 4th position. If I can do this, I will complete the step 1 of the task.

Answer 1

The problem you described is a classical Union-Find problem, which can be solved with a disjoint set algorithm. Don't re-invent the wheel.

Read about Union-Find/Disjoint set:

http://en.wikipedia.org/wiki/Disjoint-set_data_structure

Or questions:

A set union find algorithm

Union find implementation using Python

class DisjointSet(object):
def __init__(self):
    self.leader = {} # maps a member to the group's 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 algorithm can solve the problem, but I think it's an overkill, since you actually don't need the shortest distance between nodes, you just need the connected components in a graph.

Answer 2

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

Graph will look like: