3v4l.org

run code in 300+ PHP versions simultaneously
<?php $needle = '0772-51-AA-655'; $haystack = array( '0772-51-AA-6559', '0772-51-AA-6557', '0772-51-AA-6552' ); $result = findFuzzyMatches($needle, $haystack); var_dump($result); function findFuzzyMatches ($needle, $haystack, $tolerance = 1) { /* Returns (fuzzy) matches between $needle and elements of $haystack. The selected matches are those having Levenshtein distance up to $tolerance. Give $tolerance = -1 to get all matches. Return type is an associative array: the keys are the Levenshtein distance (integer), the values are sub-arrays containing the elements of $haystack having that distance. E.g.: $needle = 'abc'; $haystack = array('abc', 'abd', 'abe', 'xyz'); returns: array( 0 => array('abc'), 1 => array('abd', 'abe'), 3 => array('xyz') ) */ $matches = array(); // key: distance, value: sub-array with candidates having that distance foreach ($haystack as $candidate) { // NOTE: Slowness? Use levenshtein, which is the faster function of the two. //$distance = levenshtein($needle, $candidate); // Downside: character swaps cost 2 instead of 1. $distance = DamerauLevenshtein($needle, $candidate); if ($distance <= $tolerance || $tolerance == -1) { if (!array_key_exists($distance, $matches)) { $matches[$distance] = array(); } $matches[$distance][] = $candidate; } } return $matches; } function DamerauLevenshtein($str1, $str2) { $d = Array(); $lenStr1 = strlen($str1); $lenStr2 = strlen($str2); if ($lenStr1 == 0) { return $lenStr2; } if ($lenStr2 == 0) { return $lenStr1; } for ($i=0; $i <= $lenStr1; $i++) { $d[$i] = Array(); $d[$i][0] = $i; } for ($j=0; $j <= $lenStr2; $j++) { $d[0][$j] = $j; } for ($i=1; $i <= $lenStr1; $i++) { for ($j=1; $j <= $lenStr2; $j++) { $cost = substr($str1, $i - 1, 1) == substr($str2, $j - 1, 1) ? 0 : 1; $d[$i][$j] = min( $d[$i - 1][$j] + 1, // deletion $d[$i][$j - 1] + 1, // insertion $d[$i - 1][$j - 1] + $cost // substitution ); if ( $i > 1 && $j > 1 && substr($str1, $i - 1, 1) == substr($str2, $j - 2, 1) && substr($str1, $i - 2, 1) == substr($str2, $j - 1, 1) ) { $d[$i][$j] = min( $d[$i][$j], $d[$i - 2][$j - 2] + $cost // transposition ); } } } return $d[$lenStr1][$lenStr2]; } ?>
Finding entry points
Branch analysis from position: 0
1 jumps found. (Code = 62) Position 1 = -2
filename:       /in/5UZG3
function name:  (null)
number of ops:  11
compiled vars:  !0 = $needle, !1 = $haystack, !2 = $result
line      #* E I O op                           fetch          ext  return  operands
-------------------------------------------------------------------------------------
    3     0  E >   ASSIGN                                                   !0, '0772-51-AA-655'
    4     1        ASSIGN                                                   !1, <array>
    9     2        INIT_FCALL_BY_NAME                                       'findFuzzyMatches'
          3        SEND_VAR_EX                                              !0
          4        SEND_VAR_EX                                              !1
          5        DO_FCALL                                      0  $5      
          6        ASSIGN                                                   !2, $5
   10     7        INIT_FCALL                                               'var_dump'
          8        SEND_VAR                                                 !2
          9        DO_ICALL                                                 
  103    10      > RETURN                                                   1

Function findfuzzymatches:
Finding entry points
Branch analysis from position: 0
2 jumps found. (Code = 77) Position 1 = 5, Position 2 = 25
Branch analysis from position: 5
2 jumps found. (Code = 78) Position 1 = 6, Position 2 = 25
Branch analysis from position: 6
2 jumps found. (Code = 47) Position 1 = 13, Position 2 = 15
Branch analysis from position: 13
2 jumps found. (Code = 43) Position 1 = 16, Position 2 = 24
Branch analysis from position: 16
2 jumps found. (Code = 43) Position 1 = 19, Position 2 = 21
Branch analysis from position: 19
1 jumps found. (Code = 42) Position 1 = 5
Branch analysis from position: 5
Branch analysis from position: 21
Branch analysis from position: 24
Branch analysis from position: 15
Branch analysis from position: 25
1 jumps found. (Code = 62) Position 1 = -2
Branch analysis from position: 25
filename:       /in/5UZG3
function name:  findFuzzyMatches
number of ops:  28
compiled vars:  !0 = $needle, !1 = $haystack, !2 = $tolerance, !3 = $matches, !4 = $candidate, !5 = $distance
line      #* E I O op                           fetch          ext  return  operands
-------------------------------------------------------------------------------------
   12     0  E >   RECV                                             !0      
          1        RECV                                             !1      
          2        RECV_INIT                                        !2      1
   35     3        ASSIGN                                                   !3, <array>
   37     4      > FE_RESET_R                                       $7      !1, ->25
          5    > > FE_FETCH_R                                               $7, !4, ->25
   41     6    >   INIT_FCALL_BY_NAME                                       'DamerauLevenshtein'
          7        SEND_VAR_EX                                              !0
          8        SEND_VAR_EX                                              !4
          9        DO_FCALL                                      0  $8      
         10        ASSIGN                                                   !5, $8
   43    11        IS_SMALLER_OR_EQUAL                              ~10     !5, !2
         12      > JMPNZ_EX                                         ~10     ~10, ->15
         13    >   IS_EQUAL                                         ~11     !2, -1
         14        BOOL                                             ~10     ~11
         15    > > JMPZ                                                     ~10, ->24
   44    16    >   ARRAY_KEY_EXISTS                                 ~12     !5, !3
         17        BOOL_NOT                                         ~13     ~12
         18      > JMPZ                                                     ~13, ->21
   45    19    >   ASSIGN_DIM                                               !3, !5
         20        OP_DATA                                                  <array>
   47    21    >   FETCH_DIM_W                                      $15     !3, !5
         22        ASSIGN_DIM                                               $15
         23        OP_DATA                                                  !4
   37    24    > > JMP                                                      ->5
         25    >   FE_FREE                                                  $7
   51    26      > RETURN                                                   !3
   52    27*     > RETURN                                                   null

End of function findfuzzymatches

Function dameraulevenshtein:
Finding entry points
Branch analysis from position: 0
2 jumps found. (Code = 43) Position 1 = 9, Position 2 = 10
Branch analysis from position: 9
1 jumps found. (Code = 62) Position 1 = -2
Branch analysis from position: 10
2 jumps found. (Code = 43) Position 1 = 12, Position 2 = 13
Branch analysis from position: 12
1 jumps found. (Code = 62) Position 1 = -2
Branch analysis from position: 13
1 jumps found. (Code = 42) Position 1 = 21
Branch analysis from position: 21
2 jumps found. (Code = 44) Position 1 = 23, Position 2 = 15
Branch analysis from position: 23
1 jumps found. (Code = 42) Position 1 = 29
Branch analysis from position: 29
2 jumps found. (Code = 44) Position 1 = 31, Position 2 = 25
Branch analysis from position: 31
1 jumps found. (Code = 42) Position 1 = 127
Branch analysis from position: 127
2 jumps found. (Code = 44) Position 1 = 129, Position 2 = 33
Branch analysis from position: 129
1 jumps found. (Code = 62) Position 1 = -2
Branch analysis from position: 33
1 jumps found. (Code = 42) Position 1 = 124
Branch analysis from position: 124
2 jumps found. (Code = 44) Position 1 = 126, Position 2 = 35
Branch analysis from position: 126
2 jumps found. (Code = 44) Position 1 = 129, Position 2 = 33
Branch analysis from position: 129
Branch analysis from position: 33
Branch analysis from position: 35
2 jumps found. (Code = 43) Position 1 = 49, Position 2 = 51
Branch analysis from position: 49
1 jumps found. (Code = 42) Position 1 = 52
Branch analysis from position: 52
2 jumps found. (Code = 46) Position 1 = 76, Position 2 = 78
Branch analysis from position: 76
2 jumps found. (Code = 46) Position 1 = 79, Position 2 = 93
Branch analysis from position: 79
2 jumps found. (Code = 46) Position 1 = 94, Position 2 = 108
Branch analysis from position: 94
2 jumps found. (Code = 43) Position 1 = 109, Position 2 = 123
Branch analysis from position: 109
2 jumps found. (Code = 44) Position 1 = 126, Position 2 = 35
Branch analysis from position: 126
Branch analysis from position: 35
Branch analysis from position: 123
Branch analysis from position: 108
Branch analysis from position: 93
Branch analysis from position: 78
Branch analysis from position: 51
2 jumps found. (Code = 46) Position 1 = 76, Position 2 = 78
Branch analysis from position: 76
Branch analysis from position: 78
Branch analysis from position: 25
2 jumps found. (Code = 44) Position 1 = 31, Position 2 = 25
Branch analysis from position: 31
Branch analysis from position: 25
Branch analysis from position: 15
2 jumps found. (Code = 44) Position 1 = 23, Position 2 = 15
Branch analysis from position: 23
Branch analysis from position: 15
filename:       /in/5UZG3
function name:  DamerauLevenshtein
number of ops:  133
compiled vars:  !0 = $str1, !1 = $str2, !2 = $d, !3 = $lenStr1, !4 = $lenStr2, !5 = $i, !6 = $j, !7 = $cost
line      #* E I O op                           fetch          ext  return  operands
-------------------------------------------------------------------------------------
   54     0  E >   RECV                                             !0      
          1        RECV                                             !1      
   55     2        ASSIGN                                                   !2, <array>
   57     3        STRLEN                                           ~9      !0
          4        ASSIGN                                                   !3, ~9
   58     5        STRLEN                                           ~11     !1
          6        ASSIGN                                                   !4, ~11
   60     7        IS_EQUAL                                                 !3, 0
          8      > JMPZ                                                     ~13, ->10
   61     9    > > RETURN                                                   !4
   64    10    >   IS_EQUAL                                                 !4, 0
         11      > JMPZ                                                     ~14, ->13
   65    12    > > RETURN                                                   !3
   68    13    >   ASSIGN                                                   !5, 0
         14      > JMP                                                      ->21
   69    15    >   ASSIGN_DIM                                               !2, !5
         16        OP_DATA                                                  <array>
   70    17        FETCH_DIM_W                                      $17     !2, !5
         18        ASSIGN_DIM                                               $17, 0
         19        OP_DATA                                                  !5
   68    20        PRE_INC                                                  !5
         21    >   IS_SMALLER_OR_EQUAL                                      !5, !3
         22      > JMPNZ                                                    ~20, ->15
   73    23    >   ASSIGN                                                   !6, 0
         24      > JMP                                                      ->29
   74    25    >   FETCH_DIM_W                                      $22     !2, 0
         26        ASSIGN_DIM                                               $22, !6
         27        OP_DATA                                                  !6
   73    28        PRE_INC                                                  !6
         29    >   IS_SMALLER_OR_EQUAL                                      !6, !4
         30      > JMPNZ                                                    ~25, ->25
   77    31    >   ASSIGN                                                   !5, 1
         32      > JMP                                                      ->127
   78    33    >   ASSIGN                                                   !6, 1
         34      > JMP                                                      ->124
   79    35    >   INIT_FCALL                                               'substr'
         36        SEND_VAR                                                 !0
         37        SUB                                              ~28     !5, 1
         38        SEND_VAL                                                 ~28
         39        SEND_VAL                                                 1
         40        DO_ICALL                                         $29     
         41        INIT_FCALL                                               'substr'
         42        SEND_VAR                                                 !1
         43        SUB                                              ~30     !6, 1
         44        SEND_VAL                                                 ~30
         45        SEND_VAL                                                 1
         46        DO_ICALL                                         $31     
         47        IS_EQUAL                                                 $29, $31
         48      > JMPZ                                                     ~32, ->51
         49    >   QM_ASSIGN                                        ~33     0
         50      > JMP                                                      ->52
         51    >   QM_ASSIGN                                        ~33     1
         52    >   ASSIGN                                                   !7, ~33
   81    53        INIT_FCALL                                               'min'
   82    54        SUB                                              ~37     !5, 1
         55        FETCH_DIM_R                                      ~38     !2, ~37
         56        FETCH_DIM_R                                      ~39     ~38, !6
         57        ADD                                              ~40     ~39, 1
         58        SEND_VAL                                                 ~40
   83    59        SUB                                              ~42     !6, 1
         60        FETCH_DIM_R                                      ~41     !2, !5
         61        FETCH_DIM_R                                      ~43     ~41, ~42
         62        ADD                                              ~44     ~43, 1
         63        SEND_VAL                                                 ~44
   84    64        SUB                                              ~45     !5, 1
         65        SUB                                              ~47     !6, 1
         66        FETCH_DIM_R                                      ~46     !2, ~45
         67        FETCH_DIM_R                                      ~48     ~46, ~47
         68        ADD                                              ~49     ~48, !7
         69        SEND_VAL                                                 ~49
         70        DO_ICALL                                         $50     
   81    71        FETCH_DIM_W                                      $35     !2, !5
         72        ASSIGN_DIM                                               $35, !6
   84    73        OP_DATA                                                  $50
   88    74        IS_SMALLER                                       ~51     1, !5
         75      > JMPZ_EX                                          ~51     ~51, ->78
   89    76    >   IS_SMALLER                                       ~52     1, !6
         77        BOOL                                             ~51     ~52
         78    > > JMPZ_EX                                          ~51     ~51, ->93
   90    79    >   INIT_FCALL                                               'substr'
         80        SEND_VAR                                                 !0
         81        SUB                                              ~53     !5, 1
         82        SEND_VAL                                                 ~53
         83        SEND_VAL                                                 1
         84        DO_ICALL                                         $54     
         85        INIT_FCALL                                               'substr'
         86        SEND_VAR                                                 !1
         87        SUB                                              ~55     !6, 2
         88        SEND_VAL                                                 ~55
         89        SEND_VAL                                                 1
         90        DO_ICALL                                         $56     
         91        IS_EQUAL                                         ~57     $54, $56
         92        BOOL                                             ~51     ~57
         93    > > JMPZ_EX                                          ~51     ~51, ->108
   91    94    >   INIT_FCALL                                               'substr'
         95        SEND_VAR                                                 !0
         96        SUB                                              ~58     !5, 2
         97        SEND_VAL                                                 ~58
         98        SEND_VAL                                                 1
         99        DO_ICALL                                         $59     
        100        INIT_FCALL                                               'substr'
        101        SEND_VAR                                                 !1
        102        SUB                                              ~60     !6, 1
        103        SEND_VAL                                                 ~60
        104        SEND_VAL                                                 1
        105        DO_ICALL                                         $61     
        106        IS_EQUAL                                         ~62     $59, $61
        107        BOOL                                             ~51     ~62
        108    > > JMPZ                                                     ~51, ->123
   93   109    >   INIT_FCALL                                               'min'
   94   110        FETCH_DIM_R                                      ~65     !2, !5
        111        FETCH_DIM_R                                      ~66     ~65, !6
        112        SEND_VAL                                                 ~66
   95   113        SUB                                              ~67     !5, 2
        114        SUB                                              ~69     !6, 2
        115        FETCH_DIM_R                                      ~68     !2, ~67
        116        FETCH_DIM_R                                      ~70     ~68, ~69
        117        ADD                                              ~71     ~70, !7
        118        SEND_VAL                                                 ~71
        119        DO_ICALL                                         $72     
   93   120        FETCH_DIM_W                                      $63     !2, !5
        121        ASSIGN_DIM                                               $63, !6
   95   122        OP_DATA                                                  $72
   78   123    >   PRE_INC                                                  !6
        124    >   IS_SMALLER_OR_EQUAL                                      !6, !4
        125      > JMPNZ                                                    ~74, ->35
   77   126    >   PRE_INC                                                  !5
        127    >   IS_SMALLER_OR_EQUAL                                      !5, !3
        128      > JMPNZ                                                    ~76, ->33
  101   129    >   FETCH_DIM_R                                      ~77     !2, !3
        130        FETCH_DIM_R                                      ~78     ~77, !4
        131      > RETURN                                                   ~78
  102   132*     > RETURN                                                   null

End of function dameraulevenshtein

Generated using Vulcan Logic Dumper, using php 8.0.0


preferences:
161.54 ms | 1412 KiB | 19 Q