Most efficient way to remove special characters from string

Question

I want to remove all special characters from a string. Allowed characters are A-Z (uppercase or lowercase), numbers (0-9), underscore (_), or the dot sign (.).

I have the following, it works but I suspect (I know!) it's not very efficient:

    public static string RemoveSpecialCharacters(string str)
    {

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < str.Length; i++)
        {
            if ((str[i] >= '0' && str[i] <= '9') || (str[i] >= 'A' && str[i] <= 'z' || (str[i] == '.' || str[i] == '_')))
                sb.Append(str[i]);
        }

        return sb.ToString();
    }

What is the most efficient way to do this? What would a regular expression look like, and how does it compare with normal string manipulation?

The strings that will be cleaned will be rather short, usually between 10 and 30 characters in length.

Answer 1

I would use a String Replace with a Regular Expression searching for "special characters", replacing all characters found with an empty string.

Answer 2

This doesn't seem inefficient at all. You may be able to improve on it but you may compromise readability / maintainability.

Regards

Answer 3

I suggest creating a simple lookup table, which you can initialize in the static constructor to set any combination of characters to valid. This lets you do a quick, single check.

edit

Also, for speed, you'll want to initialize the capacity of your StringBuilder to the length of your input string. This will avoid reallocations. These two methods together will give you both speed and flexibility.

another edit

I think the compiler might optimize it out, but as a matter of style as well as efficiency, I recommend foreach instead of for.

Answer 4

Well, unless you really need to squeeze the performance out of your function, just go with what is easiest to maintain and understand. A regular expression would look like this:

For additional performance, you can either pre-compile it or just tell it to compile on first call (subsequent calls will be faster.)

public static string RemoveSpecialCharacters(string str)
{
    return Regex.Replace(str, "[^a-zA-Z0-9_.]+", "", RegexOptions.Compiled);
}

Answer 5

A regular expression will look like:

public string RemoveSpecialChars(string input)
{
    return Regex.Replace(input, @"[^0-9a-zA-Z\._]", string.Empty);
}

But if performance is highly important, I recommend you to do some benchmarks before selecting the "regex path"...

Answer 6

It seems good to me. The only improvement I would make is to initialize the StringBuilder with the length of the string.

StringBuilder sb = new StringBuilder(str.Length);

Answer 7

I'm not convinced your algorithm is anything but efficient. It's O(n) and only looks at each character once. You're not gonna get any better than that unless you magically know values before checking them.

I would however initialize the capacity of your StringBuilder to the initial size of the string. I'm guessing your perceived performance problem comes from memory reallocation.

Side note: Checking A-z is not safe. You're including [, \, ], ^, _, and `...

Side note 2: For that extra bit of efficiency, put the comparisons in an order to minimize the number of comparisons. (At worst, you're talking 8 comparisons tho, so don't think too hard.) This changes with your expected input, but one example could be:

if (str[i] >= '0' && str[i] <= 'z' && 
    (str[i] >= 'a' || str[i] <= '9' ||  (str[i] >= 'A' && str[i] <= 'Z') || 
    str[i] == '_') || str[i] == '.')

Side note 3: If for whatever reason you REALLY need this to be fast, a switch statement may be faster. The compiler should create a jump table for you, resulting in only a single comparison:

switch (str[i])
{
    case '0':
    case '1':
    .
    .
    .
    case '.':
        sb.Append(str[i]);
        break;
}

Answer 8

Why do you think that your method is not efficient? It's actually one of the most efficient ways that you can do it.

You should of course read the character into a local variable or use an enumerator to reduce the number of array accesses:

public static string RemoveSpecialCharacters(string str) {
   StringBuilder sb = new StringBuilder();
   foreach (char c in str) {
      if ((c >= '0' && c <= '9') || (c >= 'A' && c <= 'Z') | || (c >= 'a' && c <= 'z') | c == '.' || c == '_') {
         sb.Append(c);
      }
   }
   return sb.ToString();
}

One thing that makes a method like this efficient is that it scales well. The execution time will be relative to the length of the string. There is no nasty surprises if you would use it on a large string.

Edit:
I made a quick performance test, running each function a million times with a 24 character string. These are the results:

Original function: 54.5 ms.
My suggested change: 47.1 ms.
Mine with setting StringBuilder capacity: 43.3 ms.
Regular expression: 294.4 ms.

Edit 2: I added the distinction between A-Z and a-z in the code above. (I reran the performance test, and there is no noticable difference.)

Edit 3:
I tested the lookup+char[] solution, and it runs in about 13 ms.

The prize to pay is of course the initialisation of the huge lookup table and keeping it in memory. Well, it's not that much data, but it's much for such a trivial function...

private static bool[] _lookup;

static Program() {
   _lookup = new bool[65535];
   for (char c = '0'; c <= 9; c++) _lookup[c] = true;
   for (char c = 'A'; c <= 'Z'; c++) _lookup[c] = true;
   for (char c = 'a'; c <= 'z'; c++) _lookup[c] = true;
   _lookup['.'] = true;
   _lookup['_'] = true;
}

public static string RemoveSpecialCharacters(string str) {
   char[] buffer = new char[str.Length];
   int index = 0;
   foreach (char c in str) {
      if (_lookup[c]) {
         buffer[index] = c;
         index++;
      }
   }
   return new string(buffer, 0, index);
}

Answer 9

I wonder if a Regex-based replacement (possibly compiled) is faster. Would have to test that.

Other than that, you should initialize the StringBuilder with an expected length, so that the intermediate string doesn't have to be copied around while it grows.

A good number is the length of the original string, or something slightly lower (depending on the nature of the functions inputs).

Finally, you can use a lookup table (in the range 0..127) to find out whether a character is to be accepted.

Answer 10

If you're worried about speed, use pointers to edit the existing string. You could pin the string and get a pointer to it, then run a for loop over each character, overwriting each invalid character with a replacement character. It would be extremely efficient and would not require allocating any new string memory. You would also need to compile your module with the unsafe option, and add the "unsafe" modifier to your method header in order to use pointers.

static void Main(string[] args)
{
    string str = "string!$%with^&*invalid!!characters";
    Console.WriteLine( str ); //print original string
    FixMyString( str, ' ' );
    Console.WriteLine( str ); //print string again to verify that it has been modified
    Console.ReadLine(); //pause to leave command prompt open
}


public static unsafe void FixMyString( string str, char replacement_char )
{
    fixed (char* p_str = str)
    {
        char* c = p_str; //temp pointer, since p_str is read-only
        for (int i = 0; i < str.Length; i++, c++) //loop through each character in string, advancing the character pointer as well
            if (!IsValidChar(*c)) //check whether the current character is invalid
                (*c) = replacement_char; //overwrite character in existing string with replacement character
    }
}

public static bool IsValidChar( char c )
{
    return (c >= '0' && c <= '9') || (c >= 'A' && c <= 'Z') || (c >= 'a' && c <= 'z') || (c == '.' || c == '_');
    //return char.IsLetterOrDigit( c ) || c == '.' || c == '_'; //this may work as well
}

Answer 11

public static string RemoveSpecialCharacters(string str)
{
    char[] buffer = new char[str.Length];
    int idx = 0;

    foreach (char c in str)
    {
        if ((c >= '0' && c <= '9') || (c >= 'A' && c <= 'Z')
            || (c >= 'a' && c <= 'z') || (c == '.') || (c == '_'))
        {
            buffer[idx] = c;
            idx++;
        }
    }

    return new string(buffer, 0, idx);
}

Answer 12

For S&G's, Linq-ified way:

var original = "(*^%foo)(@)&^@#><>?:\":';=-+_";
var valid = new char[] { 
    'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 
    'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z', 'A', 'B', 'C', 'D', 
    'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 
    'T', 'U', 'V', 'W', 'X', 'Y', 'Z', '1', '2', '3', '4', '5', '6', '7', '8', 
    '9', '0', '.', '_' };
var result = string.Join("",
    (from x in original.ToCharArray() 
     where valid.Contains(x) select x.ToString())
        .ToArray());

I don't think this is going to be the most efficient way, however.

Answer 13

StringBuilder sb = new StringBuilder();

for (int i = 0; i < fName.Length; i++)
{
   if (char.IsLetterOrDigit(fName[i]))
    {
       sb.Append(fName[i]);
    }
}

Answer 14

public string RemoveSpecial(string evalstr)
{
StringBuilder finalstr = new StringBuilder();
            foreach(char c in evalstr){
            int charassci = Convert.ToInt16(c);
            if (!(charassci >= 33 && charassci <= 47))// special char ???
             finalstr.append(c);
            }
return finalstr.ToString();
}