Struktur data dan algoritma dalam JavaScript (5): Kemahiran algoritma

Algoritma KMP dan algoritma BM

KMP ialah algoritma klasik untuk padanan awalan dan padanan akhiran BM Dapat dilihat bahawa perbezaan antara padanan awalan dan padanan akhiran hanya dalam susunan perbandingan

Padanan awalan bermaksud: perbandingan rentetan corak dan rentetan induk adalah dari kiri ke kanan, dan pergerakan rentetan corak juga dari kiri ke kanan

Padanan akhiran bermaksud: perbandingan rentetan corak dan rentetan induk adalah dari kanan ke kiri, dan pergerakan rentetan corak dari kiri ke kanan.

Melalui bab sebelum ini jelas bahawa algoritma BF juga merupakan algoritma awalan, tetapi kecekapan padanan satu demi satu adalah sangat sombong Sememangnya, tidak perlu menyebut O(. mn). KMP, yang menjengkelkan dalam talian, banyak menerangkan mereka pada asasnya menggunakan laluan peringkat tinggi dan anda mungkin keliru >

KMP

KMP juga merupakan versi algoritma awalan yang dioptimumkan Sebab mengapa ia dipanggil KMP ialah singkatan daripada tiga nama Knuth, Morris dan Pratt Berbanding dengan BF, titik pengoptimuman algoritma KMP ialah "the jarak setiap pergerakan ke belakang" Ia akan melaraskan jarak pergerakan setiap rentetan corak secara dinamik. BF ialah 1 setiap kali,

Tidak semestinya untuk KMP

Seperti yang ditunjukkan dalam rajah, perbezaan antara pra-algoritma BF dan KMP dibandingkan

Saya membandingkan gambar dan mendapati:

Cari rentetan corak P dalam rentetan teks T. Apabila ia secara semula jadi sepadan dengan huruf keenam c, didapati tahap kedua tidak konsisten Kemudian kaedah BF adalah untuk memindahkan keseluruhan rentetan corak P pada satu tempat, dan KMP akan memindahkannya ke dua tempat .

Kami tahu kaedah pemadanan BF, tetapi kenapa KMP menggerakkan dua digit dan bukannya satu atau tiga atau empat digit?

Mari jelaskan gambar sebelumnya Rentetan pola P adalah betul apabila ia sepadan dengan ababa, dan ia adalah salah apabila ia sepadan dengan c Maka idea algoritma KMP ialah: ababa dipadankan dengan betul kami menggunakan maklumat ini untuk tidak mengalihkan "kedudukan carian" kembali ke kedudukan yang telah dibandingkan, tetapi terus mengalihkannya ke belakang, yang meningkatkan kecekapan.

Maka persoalannya, bagaimana saya tahu berapa banyak jawatan yang perlu dipindahkan?

Pengarang algoritma offset KMP ini telah meringkaskannya untuk kami:

Salin kod Kod adalah seperti berikut:

Digit peralihan = Bilangan aksara yang dipadankan - Nilai padanan separa yang sepadan

Algoritma mengimbangi hanya berkaitan dengan subrentetan, bukan rentetan teks, jadi perhatian khusus perlu diberikan di sini
Jadi bagaimana kita memahami bilangan aksara yang dipadankan dalam subrentetan dan nilai padanan separa yang sepadan?

Aksara dipadankan:

Salin kod Kod adalah seperti berikut:

T : ababababaabab

p : ababacb

Tanda merah dalam p ialah aksara yang dipadankan, yang mudah difahami

Nilai padanan separa:

Ini adalah algoritma teras, dan ia juga sukar untuk difahami

Jika:

Salin kod Kod adalah seperti berikut:

T：aaronaabbcc

P：aaronaac

Kita boleh memerhatikan teks ini Jika kita membuat ralat semasa memadankan c, di manakah langkah seterusnya berdasarkan struktur sebelumnya.

Salin kod Kod adalah seperti berikut:

aaronaabbcc
aaronaac

Maksudnya: dalam teks corak, jika permulaan dan penghujung perenggan aksara tertentu adalah sama, maka perenggan kandungan ini boleh dilangkau semasa penapisan semula jadi idea ini juga wajar

Mengetahui peraturan ini, algoritma jadual padanan separa yang diberikan adalah seperti berikut:

Pertama sekali, anda perlu memahami dua konsep: "awalan" dan "akhiran". "Awalan" merujuk kepada semua gabungan kepala rentetan kecuali aksara terakhir; "akhiran" merujuk kepada semua gabungan ekor rentetan kecuali aksara pertama.

"Nilai padanan separa" ialah panjang elemen sepunya terpanjang antara "awalan" dan "akhiran""

Mari kita lihat bahagian aaronaac jika ia adalah perlawanan BF

Anjakan BF: a,aa,aar,aaro,aaron,aarona,aaronaa,aaronaac

Jadi bagaimana pula dengan bahagian-bahagian KMP? Di sini kita perlu memperkenalkan awalan dan akhiran

Mari kita lihat dahulu keputusan jadual padanan separa KMP:

Salin kod Kod adalah seperti berikut:

a a r o n a a c

[0, 1, 0, 0, 0, 1, 2, 0]

Saya pasti keliru, jadi jangan risau, mari kita pecahkan, awalan dan akhiran

Salin kod Kod adalah seperti berikut:

Rentetan padan: "Aaron"

Awalan: A, Aa, Aar, Aaro

Akhiran: aron,ron,on,n

Kedudukan bergerak: Sebenarnya, ia adalah untuk membandingkan awalan dan akhiran setiap aksara yang dipadankan untuk melihat sama ada ia adalah sama, dan kemudian mengira jumlah panjang

Penguraian jadual padanan separa

Algoritma jadual padanan dalam KMP, dengan p mewakili awalan, n mewakili akhiran dan r mewakili hasil

Salin kod Kod adalah seperti berikut:

a, p=>0, n=>0 r = 0

aa, p=>[a], n=>[a], r = a.panjang => 1

aar, p=>[a,aa], n=>[r,ar] ,r = 0

aaro, p=>[a,aa,aar], n=>[o,ra,aro] ,r = 0

aaron p=>[a,aa,aar,aaro], n=>[n,on,ron,aron] ,r = 0

aarona, p=>[a,aa,aar,aaro,aaron], n=>[a,na,ona,rona,arona] ,r = a.lenght = 1

aaronaa, p=>[a,aa,aar,aaro,aaron,aarona], n=>[a,aa,naa,onaa,ronaa,aronaa] , r = Math.max(a.length ,aa.length) = 2

aaronaac p=>[a,aa,aar,aaro,aaron,aarona], n=>[c,ac,aac,naac,onaac,ronaac] r = 0

Sama seperti algoritma BF, mula-mula menguraikan kedudukan setiap subskrip padanan yang mungkin dan cache apabila memadankan, gunakan "jadual padanan separa" ini untuk mencari bilangan digit yang perlu dialihkan

Jadi keputusan akhir jadual padanan aaronaac ialah 0,1,0,0,0,1,2,0

KMP versi JS akan dilaksanakan di bawah, terdapat 2 jenis

Pelaksanaan KMP (1): jadual padanan caching KMP

Pelaksanaan KMP (2): kira KMP seterusnya

secara dinamik

Pelaksanaan KMP (1)

Meja padan

Perkara yang paling penting dalam algoritma KMP ialah jadual padanan Jika jadual padanan tidak diperlukan, maka ia adalah pelaksanaan BF Menambah jadual padanan adalah KMP

Jadual padanan menentukan kiraan anjakan seterusnya

Berdasarkan peraturan jadual padanan di atas, kami mereka bentuk kaedah kmpGetStrPartMatchValue

function kmpGetStrPartMatchValue(str) {
   var prefix = [];
   var suffix = [];
   var partMatch = [];
   for (var i = 0, j = str.length; i < j; i++) {
    var newStr = str.substring(0, i + 1);
    if (newStr.length == 1) {
     partMatch[i] = 0;
    } else {
     for (var k = 0; k < i; k++) {
      //前缀
      prefix[k] = newStr.slice(0, k + 1);
      //后缀
      suffix[k] = newStr.slice(-k - 1);
      //如果相等就计算大小,并放入结果集中
      if (prefix[k] == suffix[k]) {
       partMatch[i] = prefix[k].length;
      }
     }
     if (!partMatch[i]) {
      partMatch[i] = 0;
     }
    }
   }
   return partMatch;
  }

Salin selepas log masuk

Selaras sepenuhnya dengan pelaksanaan algoritma jadual padanan dalam KMP, a->aa->aar->aaro->aaron->aarona-> diuraikan melalui str.substring(0, i 1) aaronaa-aaronaac

Kemudian hitung panjang unsur sepunya melalui awalan dan akhiran dalam setiap penguraian

Algoritma Sandaran

KMP juga merupakan algoritma bahagian hadapan Anda boleh memindahkan sepenuhnya BF satu-satunya pengubahsuaian ialah BF terus menambah 1 apabila KMP berundur, kita boleh mengira nilai seterusnya melalui jadual padanan

//子循环
for (var j = 0; j < searchLength; j++) {
  //如果与主串匹配
  if (searchStr.charAt(j) == sourceStr.charAt(i)) {
    //如果是匹配完成
    if (j == searchLength - 1) {
     result = i - j;
     break;
    } else {
     //如果匹配到了，就继续循环，i++是用来增加主串的下标位
     i++;
    }
  } else {
   //在子串的匹配中i是被叠加了
   if (j > 1 && part[j - 1] > 0) {
    i += (i - j - part[j - 1]);
   } else {
    //移动一位
    i = (i - j)
   }
   break;
  }
}

Salin selepas log masuk

Tanda merah ialah titik teras KMP Nilai seterusnya = bilangan aksara yang dipadankan - nilai padanan separa yang sepadan

Algoritma KMP lengkap

<!doctype html><div id="test2"><div><script type="text/javascript">
 

  function kmpGetStrPartMatchValue(str) {
   var prefix = [];
   var suffix = [];
   var partMatch = [];
   for (var i = 0, j = str.length; i < j; i++) {
    var newStr = str.substring(0, i + 1);
    if (newStr.length == 1) {
     partMatch[i] = 0;
    } else {
     for (var k = 0; k < i; k++) {
      //取前缀
      prefix[k] = newStr.slice(0, k + 1);
      suffix[k] = newStr.slice(-k - 1);
      if (prefix[k] == suffix[k]) {
       partMatch[i] = prefix[k].length;
      }
     }
     if (!partMatch[i]) {
      partMatch[i] = 0;
     }
    }
   }
   return partMatch;
  }



function KMP(sourceStr, searchStr) {
  //生成匹配表
  var part     = kmpGetStrPartMatchValue(searchStr);
  var sourceLength = sourceStr.length;
  var searchLength = searchStr.length;
  var result;
  var i = 0;
  var j = 0;

  for (; i < sourceStr.length; i++) { //最外层循环，主串

    //子循环
    for (var j = 0; j < searchLength; j++) {
      //如果与主串匹配
      if (searchStr.charAt(j) == sourceStr.charAt(i)) {
        //如果是匹配完成
        if (j == searchLength - 1) {
         result = i - j;
         break;
        } else {
         //如果匹配到了，就继续循环，i++是用来增加主串的下标位
         i++;
        }
      } else {
       //在子串的匹配中i是被叠加了
       if (j > 1 && part[j - 1] > 0) {
        i += (i - j - part[j - 1]);
       } else {
        //移动一位
        i = (i - j)
       }
       break;
      }
    }

    if (result || result == 0) {
     break;
    }
  }


  if (result || result == 0) {
   return result
  } else {
   return -1;
  }
}

 var s = "BBC ABCDAB ABCDABCDABDE";
 var t = "ABCDABD";


 show('indexOf',function() {
  return s.indexOf(t)
 })

 show('KMP',function() {
  return KMP(s,t)
 })

 function show(bf_name,fn) {
  var myDate = +new Date()
  var r = fn();
  var div = document.createElement('div')
  div.innerHTML = bf_name +'算法,搜索位置:' + r + ",耗时" + (+new Date() - myDate) + "ms";
   document.getElementById("test2").appendChild(div);
 }


</script></div></div>

Salin selepas log masuk

KMP（二）

第一种kmp的算法很明显，是通过缓存查找匹配表也就是常见的空间换时间了。那么另一种就是时时查找的算法，通过传递一个具体的完成字符串，算出这个匹配值出来，原理都一样

生成缓存表的时候是整体全部算出来的，我们现在等于只要挑其中的一条就可以了，那么只要算法定位到当然的匹配即可

next算法

function next(str) {
  var prefix = [];
  var suffix = [];
  var partMatch;
  var i = str.length
  var newStr = str.substring(0, i + 1);
  for (var k = 0; k < i; k++) {
   //取前缀
   prefix[k] = newStr.slice(0, k + 1);
   suffix[k] = newStr.slice(-k - 1);
   if (prefix[k] == suffix[k]) {
    partMatch = prefix[k].length;
   }
  }
  if (!partMatch) {
   partMatch = 0;
  }
  return partMatch;
}

Salin selepas log masuk

其实跟匹配表是一样的，去掉了循环直接定位到当前已成功匹配的串了

完整的KMP.next算法

<!doctype html><div id="testnext"><div><script type="text/javascript">
 
  function next(str) {
    var prefix = [];
    var suffix = [];
    var partMatch;
    var i = str.length
    var newStr = str.substring(0, i + 1);
    for (var k = 0; k < i; k++) {
     //取前缀
     prefix[k] = newStr.slice(0, k + 1);
     suffix[k] = newStr.slice(-k - 1);
     if (prefix[k] == suffix[k]) {
      partMatch = prefix[k].length;
     }
    }
    if (!partMatch) {
     partMatch = 0;
    }
    return partMatch;
  }

  function KMP(sourceStr, searchStr) {
    var sourceLength = sourceStr.length;
    var searchLength = searchStr.length;
    var result;
    var i = 0;
    var j = 0;

    for (; i < sourceStr.length; i++) { //最外层循环，主串

      //子循环
      for (var j = 0; j < searchLength; j++) {
        //如果与主串匹配
        if (searchStr.charAt(j) == sourceStr.charAt(i)) {
          //如果是匹配完成
          if (j == searchLength - 1) {
           result = i - j;
           break;
          } else {
           //如果匹配到了，就继续循环，i++是用来增加主串的下标位
           i++;
          }
        } else {
         if (j > 1) {
          i += i - next(searchStr.slice(0,j));
         } else {
          //移动一位
          i = (i - j)
         }
         break;
        }
      }

      if (result || result == 0) {
       break;
      }
    }


    if (result || result == 0) {
     return result
    } else {
     return -1;
    }
  }

 var s = "BBC ABCDAB ABCDABCDABDE";
 var t = "ABCDAB";


  show('indexOf',function() {
   return s.indexOf(t)
  })

  show('KMP.next',function() {
   return KMP(s,t)
  })

  function show(bf_name,fn) {
   var myDate = +new Date()
   var r = fn();
   var div = document.createElement('div')
   div.innerHTML = bf_name +'算法,搜索位置:' + r + ",耗时" + (+new Date() - myDate) + "ms";
    document.getElementById("testnext").appendChild(div);
  }

</script></div></div>

Salin selepas log masuk

git代码下载: https://github.com/JsAaron/data_structure