Algo: replace chars of string to find the correct word

user_7285874 0
Viewed 41

I have a string from OCR which contains some errors.

For example "2SQ41S" in place of "250415", i have a dictionary for the possible replacements:

  • O/Q can be replaced by 0,
  • S can be replaced by 5...

I can calculate the checksum to be sure that the good word is found.

Here is the function recursive which doesn't work, it will be stopped when startPosition>=6, it's before the correct word was found:

        public void CombinaisonTest()
        {
            string date = "2SO41S";
            Dictionary<char, String[]> replaceDictionary= new Dictionary<char, String[]>()
            {
                {'O', new []{"Q", "0"}},
                {'S', new []{"8", "5", "B"}}
            };
            String result = "";
            var r = combinations2(date, 0, replaceDictionary);
            Console.WriteLine("Date: " + date);
            Console.WriteLine("R: " + r);
        }

        public string combinations2(string date, int startPosition, Dictionary<char, String[]> dictionary)
        {
            Console.WriteLine("Call function " + date + ", " + startPosition);
            if (string.Join("", date).Equals("250415")) //need to calculate checksum
            {
                Console.WriteLine("Found: " + date);
                return date;
            }
            if (startPosition >= date.Length)
            {
                Console.WriteLine("Not Found: ");
                return "";
            }
            for (int i = startPosition; i < date.Length; i++)
            {
                if (dictionary.ContainsKey(date.ToCharArray()[i]))
                {
                    foreach (var value in dictionary[date.ToCharArray()[i]])
                    {
                        return combinations2(date.Remove(i, 1).Insert(i, value), startPosition + 1, dictionary);
                    }
                }
                else
                {
                    return combinations2(date, i + 1, dictionary);
                }
               
            }
            return combinations2(date, startPosition + 1, dictionary);
        }

Do you have any ideas for the corrections, please? Thank you.

string-matching checksum algorithm
1 Answers

There are a couple of issues with the code. The first is that when iterating through the values in the dictionary, it returns after checking the first one, so it will only ever try and substitute Q for 0 and 8 for S. The second is that you are attempting two methods of processing the characters in the string: iterative AND recursive. You don't need to iterate over the index i with a for loop and also use recursion.

Another issue (which isn't a problem in your use case but stops the algorithm being more generic) is that the algorithm attempts to do a substitution in every case where an ambiguous character is encountered, as well as iterating over each value in the dictionary you should also consider the case where the character is left unmodified.

The function can be changed to remove the outer for loop and iterate over the values in the dictionary, test each one (recursing over the remainder of the string) and only return if a match is found. A simple way to do this is to store the result in a string and only return it if it is not the empty string (since your function returns the empty string when no match is found). If all the values in the dictionary have been tried and no match has been found, then it tries recursing without modifying the string.

    public string combinations2(string date, int startPosition, Dictionary<char, String[]> dictionary)
    {
        Console.WriteLine("Call function " + date + ", " + startPosition);
        if (string.Join("", date).Equals("250415")) //need to calculate checksum
        {
            Console.WriteLine("Found: " + date);
            return date;
        }
        if (startPosition >= date.Length)
        {
            Console.WriteLine("Not Found: ");
            return "";
        }
        if (dictionary.ContainsKey(date.ToCharArray()[startPosition]))
        {
            foreach (var value in dictionary[date.ToCharArray()[startPosition]])
            {
                string result = combinations2(date.Remove(startPosition, 1).Insert(startPosition, value), startPosition + 1, dictionary);
                if(result != "")
                    return result;
            }
        }
        return combinations2(date, startPosition + 1, dictionary);                                                 
    }
user_6963910
Related