4
\$\begingroup\$

(This problem is related to Simple string-split by root and sufix algorithm)

There are many ways to find a "common root" of a list of similar strings, that begins with the same substring... The question is what the best way (faster and elegant)? Do you know a book or library with these algorithms?

Example: in the set {"foo2", "foo1", "foofo"} the root is "foo".

In practical use we need also ignore extrange itens, so we can expect the same "foo" root in the set {"hello", "foo2", "foo1", "foofo", "bye"}. A "root minimal length" parameter is also a practical issue.

Here is a sample and a first candidate algorithm:

  $words = array('i', 'me', 'my', 'myself', 'we', 'our', 'ours', 'ourselves', 'you', 'your', 'yours',
   'yourself', 'yourselves', 'he', 'him', 'his', 'himself', 'she', 'her', 'hers', 'herself',
   'it', 'its', 'itself', 'they', 'them', 'their', 'theirs', 'themselves', 'what', 'which',
   'who', 'whom', 'this', 'that', 'these', 'those', 'am', 'is', 'are', 'was', 'were', 'be',
   'been', 'being', 'have', 'has', 'had', 'having', 'do', 'does', 'did', 'doing', 'a', 'an',
   'the', 'and', 'but', 'if', 'or', 'because', 'as', 'until', 'while', 'of', 'at', 'by', 'for',
   'with', 'about', 'against', 'between', 'into', 'through', 'during', 'before', 'after',
   'above', 'below', 'to', 'from', 'up', 'down', 'in', 'out', 'on', 'off', 'over', 'under',
   'again', 'further', 'then', 'once', 'here', 'there', 'when', 'where', 'why', 'how', 'all',
   'any', 'both', 'each', 'few', 'more', 'most', 'other', 'some', 'such', 'no', 'nor', 'not',
   'only', 'own', 'same', 'so', 'than', 'too', 'very', 's', 't', 'can', 'will', 'just', 'don',
   'should', 'now');

  /**
   * Get the common start-string of two strings.  
   * @param $a string. 
   * @param $b string with probable common root.
   * @return string $root or empty.
   * @see this function can feed the root for str_splitByRoot() function.
   */
  function str_getRoot($a,$b) {
        $rootLen = strspn($b ^ $a, "\0"); // length before difference.
        return substr($a,0,$rootLen);
  }

  /**
   * Get the common start-string of many strings.  
   * The algorithm splits the string by its differences.
   * @param $a array of strings. 
   * @param $b string with probable common root, or integer for array index.
   * @return array of strings with $root and family.
   */
  function array_getRoot($a,$b='',$minLen=1) {
    if (is_integer($b)) 
        $b = $a[$b];
    if (!$b) $b=$a[0];
    $family = array();                
    foreach ($a as $item) {
        $r = str_getRoot($item,$b);
        if (strlen($r)>=$minLen) {
            $family[]=$item;
            if ($r!=$b) $b=$r;
        } //if
    } // for
    array_unshift($family,$b);
    return  $family;
  }

Applying in the example:

$list = array("foo2", "hello", "foo1", "foofo", "bye");
$fam = array_getRoot($list);
print "\nThe root of list is ".array_shift($fam); // foo

Using to show the roots of the $words list:

  sort($words); // not necessary
  foreach($words as $i){
       $fam4 = array_getRoot($words,$i,4);
       $root = array_shift($fam4);
       if (count($fam4)>1)
            print "\n * $i - ($root) ".join(', ',$fam4);
       else { // repeate da same procedure:
            $fam3 = array_getRoot($words,$i,3);
            $root = array_shift($fam3);
            if (count($fam3)>1)
                 print "\n * $i - ($root) ".join(', ',$fam3);
       }
  }

Some results:

* about - (abo) about, above
* again - (again) again, against
* her   - (her) her, here, hers, herself
* hers  - (hers) hers, herself
* you   - (you) you, your, yours, yourself, yourselves
* yourself - (your) your, yours, yourself, yourselves
\$\endgroup\$
1
\$\begingroup\$

(this is not a good answer because... the answer needs performance analysis and comparison with alternative algorithms)

Only to show a tested and "unified" (str+array) algorithm... A "code" based on the defined (see question's statement) functions,

  function str_getRoot2($a,$b='',$minLen=1) { // "2" to avoid recurrence
    if (is_array($a)) // and $b is a seed.
       return array_getRoot($a,$b,$minLen);
    else  // $b is a root
       return str_getRoot($a,$b);
  }

Complete code, with an aditional retFamily parameter, and recurrence:

  /**
   * Get the commom start-string of two or more strings.  
   * @version v1.2 of 2015-06-11.
   * @param $a mix, string for final operation, or array for scan. 
   * @param $b string with probable commom root, or integer for array index.
   * @param $retFamily boolean for show "family".
   * @return string $root.
   * @see http://codereview.stackexchange.com/q/92700
   */
  function str_getRoot($a,$b='',$minLen=1,$retFamily=false) {
    if (is_array($a)) { // $b is a seed.
        $family = array();  
        if (is_integer($b))
            $b = $a[$b];
        if (count($a)>1) {
            foreach ($a as $item) if ($item) {
                if (is_array($item)) die("array of array is invalid");
                if (!$b) $b=$item; // or trim($b)..trim($item)
                $r = str_getRoot($item,$b,$minLen); // go to str
                if ($r) {
                   if ($retFamily) $family[]=$item;
                   if ($r!=$b) $b=$r;
                } //if
            } // for            
        } elseif (isset($a) && count($a)>0)
            $family[]= $b = $a[0];
        if ($retFamily) {
            array_unshift($family,$b);
            return $family;
        } else
            return $b;
    } else {  // $b is a root
        $rooLen = strspn($b ^ $a, "\0"); // split by diff
        return ($rooLen>=$minLen)? substr($a,0,$rooLen): '';        
    }
  }

Examples of use: get family array with $fam4 = str_getRoot($words,'yourself',4); or get specific root of a pair by str_getRoot('yourself','your');

\$\endgroup\$
  • \$\begingroup\$ @Quill Hi, I edited, check if explanation better. The aim was only to copy/paste my original (tested) code, I prefer to discuss this one. \$\endgroup\$ – Peter Krauss Jul 11 '15 at 19:30

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.