Simple string-split by root and sufix algorithm

Question

A classic problem to split a string into its "root and suffix":

• (Stemming) The word "walk" is the base form for word "walking" (suffix is "ing");
• The file path /var/www is the base path of /var/www/myApp;
• The string doi:10.1038/ncomms is the URN-prefix for doi:10.1038/ncomms7368 and doi:10.1038/ncomms7666;
• The word "hello" is not a root for "walking" (suffix is "walking");

There are many ways to implement the same algorithm, so, what is the best? Examples in PHP, but valid for any language.

/**
 * Splits a string by its root and sufix.
 * @param $str string input
 * @param $root string empty when no root, or start string
 * @return array (rootFlag,sufix) 
 */
function  str_splitByRoot($str, $root){
    ...
}

---

Algorithms str_splitByRoot1(), str_splitByRoot2(), ..., str_splitByRoot5() or other (show more if you know). All do the same thing, are valid solutions.

function  str_splitByRoot1($str, $root){
    if (strpos($str,$root)===0)
        return array($root, substr($str, strlen($root)) );
    else 
        return array( '', $str );
}

function  str_splitByRoot2($str, $root){
    $rootLen = strspn($str ^ $root, "\0");
    return array( substr($root,0,$rootLen), substr($str,$rootLen) );
}

function  str_splitByRoot3($str, $root){
    $s = explode($root,$str);
    return ( count($s)>1  && !array_shift($s) )? 
      array($root,join($root,$s)): 
      array('',$str);
}

function  str_splitByRoot4($str, $root){
    // to generalize need a secure regex, something like
    // $regex = str_replace(array('/','.','-'),array('\\/','\\.','\\-'),$root);
    $suffix = preg_replace("/^$root/",$str,1,$n);
    return $n? 
      array($root,$suffix): 
      array('',$str);
}

function  str_splitByRoot5($str, $root){
    // need also $root translating as algorithm 4.
    if (preg_match("/^$root(.+)$/",$str,$m))
          return array($root,$m[1]);
    else 
          return array('',$str);
}

The first is the traditional way. The last (algorithms 4 and 5) use regular expression, the second trim excess garbage from strings that are null terminated; and the third remember that the algorithm is a kind of split (explode function).

All can be used with

function str_sepByRoot($str,$root){
   return join(' * ',str_splitByRoot($str,$root)); 
}
print "\n".str_sepByRoot("walking","walk");
print "\n".str_sepByRoot("hello","walk");
print "\n".str_sepByRoot("walking-walk-walk","walk");
print "\n".str_sepByRoot("/var/www/myApp","/var/www/");
print "\n".str_sepByRoot("10.1038/ncomms7368","10.1038/ncomms");

returning

   walk * ing
    * hello
   walk * ing-walk-walk
   /var/www/ * myApp
   10.1038/ncomms * 7368

Answer 1

About "best thing"... The "principle of simplest is best" seems valid. The number of commands, and the computational simplicity of each command.

• str_splitByRoot1: 2 fast commands (strpos and substr) and 1 condition and strlen
• str_splitByRoot2: 2 fast commands (substr) and 1 to be checked (strspn+str ^ str)
• str_splitByRoot2 optimized: 1 fast command (substr), 1 to be checked (strspn) and 1 condition.
• ...

So, my doubt was about strspn+str ^ str performance... And its time struck me most, was near time for str_splitByRoot1...

  $str_splitByRoot = array(
       function  ($str, $root){  // str_splitByRoot1()
            if (strpos($str,$root)===0)
                return array($root, substr($str, strlen($root)) );
           else 
                   return array( '', $str );
       },

       function  ($str, $root){ //str_splitByRoot2()
           $rootLen = strspn($str ^ $root, "\0");
           return array( substr($root,0,$rootLen), substr($str,$rootLen) );
       },
       function  ($str, $root){ //str_splitByRoot2() optimized
           $rootLen = strspn($str ^ $root, "\0");
           return array( $rootLen?$root:'' , substr($str,$rootLen) );
       },

       function  ($str, $root){  //str_splitByRoot3()
         $s = explode($root,$str);
         return ( count($s)>1  && !array_shift($s) )? 
             array($root,join($root,$s)): 
             array('',$str);
       }   

       function ($str, $root){ // str_splitByRoot5
            $root2 = str_replace(array('/','.','-'),array('\\/','\\.','\\-'),$root);
           if (preg_match("/^$root2(.+)$/",$str,$m))
                 return array($root,$m[1]);
           else 
                 return array('',$str);
       }
  );


  function str_sepByRoot($i,$str,$root){
       global $str_splitByRoot;
       global $debug;
            $func = $str_splitByRoot[$i];
            $s = join(' * ', call_user_func($str_splitByRoot[$i],$str,$root)); // $func($str,$root));
            if ($s &&  $debug)
                 print "\n ___ $s";
  }

  $debug=0;
  for ($i=0; $i<count($str_splitByRoot); $i++) {
       print "\n--- $i ---";
       $time = microtime(true); // time in Microseconds
       for($j=0;($j<333 && !$debug) || ($debug && $j<1); $j++){
            str_sepByRoot($i,"walking","walk");
            str_sepByRoot($i,"hello","walk");
            str_sepByRoot($i,"walking-walk-walk","walk");
            str_sepByRoot($i,"/var/www/myApp","/var/www/");
            str_sepByRoot($i,"DOI:10.1038/ncomms7368","DOI:10.1038/ncomms");     
       }
       echo "\n", (microtime(true) - $time) . ' elapsed';
  }

Result:

--- 0 ---
0.0037140846252441 elapsed
--- 1 ---
0.0045409202575684 elapsed
--- 2 ---
0.0040040016174316 elapsed
--- 3 ---
0.0088369846343994 elapsed
--- 4 ---
0.0075829029083252 elapsed
--- 5 ---
0.0037930011749268 elapsed

Conclusion, using str_splitByRoot1 as reference (100%),

• str_splitByRoot2 optimized is ~105% , so for practical use it's as good as str_splitByRoot1.

• str_splitByRoot2 is ~115%, something good when compared with str_splitByRoot3 (~125%).

• str_splitByRoot5 is 225%... as expected, the worst (even without str_replace regex escapes).

---

... But, the performance changes (!) when using a big root, an Lorem ipsum of 800 words. The performance profile changed to:

• str_splitByRoot2 (optimized or not) ~244%... bad!

• str_splitByRoot3 (with direct split by explode) is ~120%, very good!

• str_splitByRoot5 (regex) ~390%, the worst of course.

So, the only that shows more "stability" (~120%) about root length was str_splitByRoot5, and str_splitByRoot2 is not a good replacement for str_splitByRoot1 in the context of big roots.