Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

Provided a starting string initialString, and a particular alphabet of allowed characters {"A","B","C","D","E",...}, how can I generate the set of all strings such that EditDistance[initialString,setElement] = k, where k is specified as desired? How can I do the same if I only consider HammingDistance?

Rather, I should say, how do we do the above without generating all of the Tuples of relevant length, then checking each one for EditDistance or HammingDistance, which is probably the most naive way to proceed?

Here's a partial example of that naive strategy (partial because for EditDistance we need to generate tuples of the string length of the initial string $\pm \space k$):

k = 1;

stringTestLength = 8;

alphabet = {"0", "1", "R"};

tuples = Map[StringJoin, Tuples[alphabet, stringTestLength]];

testString = "00000000"

distanceOneList = {};
editDistanceCounter = 0;
For[i = 1, i <= Length[tuples], i++,
  If[EditDistance[tuples[[i]], testString] == k,
    editDistanceCounter += 1;
    distanceOneList = Append[distanceOneList, tuples[[i]]];
    ];
  ];

distanceOneList
editDistanceCounter

The output here is of course the following length sixteen array:

{"00000001", "0000000Q", "00000010", "000000Q0", "00000100", "00000Q00", "00001000", "0000Q000", "00010000", "000Q0000", "00100000", "00Q00000", "01000000", "0Q000000", "10000000", "Q0000000"};

The "real" answer for EditDistance is 1 (for the length 7 tuple set) + 19 (for the length 9 tuple set) + 16 (for the length 8 = length of the initial string) tuple set. Thus, there are 36 strings over this alphabet within EditDistance k = 1 of the initial string "00000000".

share|improve this question

1 Answer 1

up vote 1 down vote accepted
kAwayWordsF[str_, dist_, alph_, strlen_] := Module[{len = StringLength[str], dict}, 
    dict = StringJoin /@ Tuples[alph, strlen]; 
     With[{nf = Nearest[dict]},  
       Complement[nf[str, {Infinity, dist}], nf[str, {Infinity, dist - 1}]]]]   
kAwayWordsF["00000000",1,{"0","1","Q"},8]
(* {"00000001", "0000000Q", "00000010", "000000Q0", "00000100", "00000Q00", "00001000",
    "0000Q000", "00010000", "000Q0000", "00100000", "00Q00000", "01000000", "0Q000000",
    "10000000","Q0000000"} *)
kAwayWordsF["00000000",2,{"0","1","Q"},7]
(* {"0000001", "000000Q", "0000010", "00000Q0", "0000100", "0000Q00","0001000",
   "000Q000", "0010000", "00Q0000", "0100000", "0Q00000","1000000", "Q000000"}  *)

Update: Removing the restriction that target strings have the same string length as the teststring:

distKWordsF[str_, dist_, alph_] := Module[{len = StringLength[str], dict},
   dict = StringJoin /@ Join @@ (Tuples[alph, #] & /@ Range[len - dist, len + dist]);
   With[{nf = Nearest[dict]}, 
      Complement[nf[str, {Infinity, dist}], nf[str, {Infinity, dist - 1}]]]]
distKWordsF["00000000", 1, {"0", "1", "Q"}]
 (*{"0000000","000000000","000000001","00000000Q","00000001","000000010",
    "0000000Q","0000000Q0", "00000010","000000100","000000Q0","000000Q00",
    "00000100", "000001000","00000Q00","00000Q000","00001000","000010000",
   "0000Q000","0000Q0000","00010000","000100000","000Q0000","000Q00000",
   "00100000","001000000", "00Q00000","00Q000000","01000000","010000000","0Q000000",
   "0Q0000000","10000000","100000000","Q0000000","Q00000000"}*)
(Length@distKWordsF["00000000", #, {"0", "1", "Q"}]) & /@ {1, 2, 3, 4, 5}
(*{{36,472,3740,22096,110036}*)
share|improve this answer
    
Great! So this is for the HammingDistance case. Is there a way to get Nearest to work for EditDistance? –  Cray Apr 20 at 11:00
    
@Cray, this is for the EditDistance b/c the default DistanceFunction for Nearest with string data is EditDistance. –  kguler Apr 20 at 11:14
    
Ah, I see, see we just need to join / concatenate the answers for $\pm k$ length strings, no? –  Cray Apr 20 at 11:15
    
Not sure how to deal with HammingDistance. First, DistanceFunction option is available only for the two-argument input pattern for Nearest; the syntax Nearest[data, DistanceFunction->sth] does not work, so we need to use the form to map Nearest[data,#,DistanceFunction->sth]& to the list of target strings (and this is much slower than the approach nf=Nearest[data]; nf/@targetlist. Second, HammingDistance only works for strings with equal stringlengths ... –  kguler Apr 20 at 11:40
    
... Regarding "joining answers for +-k length strings", I don't think it would work (EditDistance is always less than or equal to HammingDistance) –  kguler Apr 20 at 11:41

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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