I'm trying to align a sequence of characters together, I found that sequence alignment algorithms which use dynamic programming like Needleman-Wunsch or Smith–Waterman only align one character with one character beside allowing character substitution, deletion or insertion.

For example, if I have a set of similarly sounding characters, like

monir, monier, muneer, munir, mounir, mouneer

The alignment algorithm will produce the following output

m u n i - r
| | | |   |
m o n e e r

Is there a way to adapt these algorithms (or an alternative algorithm) to consider aligning/substituting character with more than one character in order to output something like

m u n i  r
| | | |  |
m o n ee r

Please note that, I'm using the standard java implementation for these algorithms and I don't have a predefined list of similarly sounding characters, so I'm trying to aligning the similar words together in order to extract these alignments.

  • 1
    $\begingroup$ Why don't you just merge gaps into neighbouring mismatches? $\endgroup$
    – Raphael
    Apr 24 '15 at 14:01
  • $\begingroup$ @Raphael the algorithm compare character by character to get the score of matching the characters and the gaps should not be always applicable to be matched with its neighbors $\endgroup$
    – vanilla
    Apr 24 '15 at 20:20
  • $\begingroup$ Why not? When will it be? $\endgroup$
    – Raphael
    Apr 24 '15 at 20:38
  • $\begingroup$ @Raphael consider these strings, how can you do that? The normal alignment will produce: (- a l s h o u a - i b i / e - l s h - - a e e b y) but actually, I need it to be aligned like (a l sh ou a i b i / e l sh - a ee b y) $\endgroup$
    – vanilla
    Apr 24 '15 at 21:30
  • $\begingroup$ You will have to make up your mind. In the question you say that the alignments are supposed to yield (candidates for) similar-sounding (groups of) characters. Now you talk of how things "need" to be. $\endgroup$
    – Raphael
    May 4 '15 at 8:38

If I understood your problem correctly, a trie data structure may help you. The main challenge would be after the first mismatch, match the upcomming characters. I'm not sure how I would hack it, but it may not be that hard.

Hope it helps. Regards

  • 1
    $\begingroup$ Welcome to Computer Science! Thanks for contributing but this is far too vague for an answer. You're basically saying, "Tries might work but they might not. And maybe they're really hard to use for this. I dunno, really." That would be OK for a comment but it's not an answer. $\endgroup$ May 2 '15 at 16:09
  • $\begingroup$ Since you cannot comment yet, one possibility is to flesh out what you said, provided it is correct. $\endgroup$
    – babou
    May 2 '15 at 17:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.