Comment implémenter la sous-séquence commune la plus longue en javascript

La séquence commune la plus longue (séquence commune la plus longue) et la sous-chaîne commune la plus longue (sous-chaîne commune la plus longue) ne sont pas la même chose. L'article suivant vous présente principalement les informations pertinentes sur l'implémentation de la sous-séquence commune la plus longue en JavaScript. les amis dans le besoin peuvent s'y référer.

Introduction

La sous-séquence commune la plus longue LCS consiste à extraire tous les éléments possibles des deux séquences X et Y données. Les caractères supplémentaires possibles sont disposés dans l’ordre dans lequel ils sont disposés dans la séquence originale. L'algorithme pour les problèmes LCS a un large éventail d'utilisations. Par exemple, dans la gestion de différentes versions de logiciels, l'algorithme LCS est utilisé pour trouver les similitudes et les différences entre l'ancienne et la nouvelle version dans les tests de logiciels. utilisé pour comparer des séquences enregistrées et rejouées ; dans le domaine du génie génétique, l'algorithme LCS est utilisé. L'algorithme vérifie les similitudes et les différences entre le brin d'ADN du patient et le brin d'ADN de la liaison dans le système anti-plagiat, l'algorithme LCS est utilisé ; utilisé pour vérifier le taux de plagiat du journal. L'algorithme LCS peut également être utilisé pour la mesure de similarité de code de programme, la récupération de séquences d'exécution humaine, la mise en correspondance de segments vidéo, etc., de sorte que la recherche sur l'algorithme LCS a une grande valeur d'application.

Concepts de base

Sous-séquence : Une sous-séquence d'une séquence spécifique est constituée de zéro ou plusieurs éléments dans une séquence donnée Le résultat obtenu après l'avoir supprimé ( sans changer l'ordre relatif entre les éléments). Par exemple, les sous-séquences de la séquence 23195a5eab8013c21303d3d24e81fe27 sont : 4e2154b1242725e74a11c55ea3967ed3, 2cf3a2d5a55d4ffa7aceebabd439c436, 6d2941b5735d6dffd2ee4b8fbaa92c61 m(i-1, j-1) + 1 (m(i, j) ne peut pas être inférieur à m(i-1, j-1) + 1, il y a plusieurs raisons évidemment), alors on peut en déduire le résultat contradictoire que m(i-1, j-1) n'est pas le plus long.

Le second est un peu délicat. Lorsque A[i] != B[j], c'est toujours une réfutation, en supposant que m(i, j) > max( m(i-1, j), m(i, j-1) ).

Par hypothèse de réfutation, nous pouvons obtenir m(i, j) > On peut en déduire que A[i] doit être dans la séquence LCS correspondant à m(i, j) (des preuves contradictoires sont disponibles). Et puisque A[i] != B[j], B[j] ne doit pas être dans la séquence LCS correspondant à m(i, j). On peut donc en déduire que m(i, j) = m(i, j-1). Cela conduit à des résultats qui contredisent de toute façon l’hypothèse.

Obtenez une certification.

Nous utilisons maintenant l'équation ci-dessous pour continuer à remplir le tableau.

La mise en œuvre du programme

//by 司徒正美
function LCS(str1, str2){
  var rows = str1.split("")
  rows.unshift("")
  var cols = str2.split("")
  cols.unshift("")
  var m = rows.length 
  var n = cols.length 
  var dp = []
  for(var i = 0; i < m; i++){ 
   dp[i] = []
   for(var j = 0; j < n; j++){ 
    if(i === 0 || j === 0){
     dp[i][j] = 0
     continue
    }
    
    if(rows[i] === cols[j]){ 
     dp[i][j] = dp[i-1][j-1] + 1 //对角＋1
    }else{
     dp[i][j] = Math.max( dp[i-1][j], dp[i][j-1]) //对左边，上边取最大
    }
   }
   console.log(dp[i].join(""))//调试
  } 
  return dp[i-1][j-1]
 }

LCS peut être encore simplifiée en déplaçant la position et en éliminant le besoin de générer de nouveaux tableaux

//by司徒正美
function LCS(str1, str2){
 var m = str1.length 
 var n = str2.length
 var dp = [new Array(n+1).fill(0)] //第一行全是0
 for(var i = 1; i <= m; i++){ //一共有m+1行
  dp[i] = [0] //第一列全是0
  for(var j = 1; j <= n; j++){//一共有n+1列
   if(str1[i-1] === str2[j-1]){ 
    //注意这里，str1的第一个字符是在第二列中，因此要减1，str2同理
    dp[i][j] = dp[i-1][j-1] + 1 //对角＋1
   } else {
     dp[i][j] = Math.max( dp[i-1][j], dp[i][j-1]) 
   }
  }
 } 
 return dp[m][n];
}

Imprimer un LCS

Nous allons donner la fonction d'impression et voir comment en imprimer un en premier. Nous commençons à regarder depuis le coin inférieur droit et terminons par la ligne supérieure. La chaîne cible est donc construite dans l’ordre inverse. Afin d'éviter d'utiliser des quantités intermédiaires gênantes telles que stringBuffer, nous pouvons l'implémenter de manière récursive. Chaque fois que le programme est exécuté, une seule chaîne est renvoyée, sinon une chaîne vide est renvoyée, en utilisant printLCS(x,y,...) +. str[ i] sont ajoutés pour obtenir la chaîne dont nous avons besoin.

Écrivons une autre méthode pour vérifier si la chaîne que nous obtenons est une vraie chaîne LCS. En tant que personne qui travaille déjà, je ne peux pas écrire de code comme un étudiant à l'école et le mettre en ligne sans effectuer de tests unitaires sur lesquels d'autres peuvent intervenir.

//by 司徒正美，打印一个LCS
function printLCS(dp, str1, str2, i, j){
 if (i == 0 || j == 0){
  return "";
 }
 if( str1[i-1] == str2[j-1] ){
  return printLCS(dp, str1, str2, i-1, j-1) + str1[i-1];
 }else{
  if (dp[i][j-1] > dp[i-1][j]){
   return printLCS(dp, str1, str2, i, j-1);
  }else{
   return printLCS(dp, str1, str2, i-1, j);
  }
 }
}
//by司徒正美， 将目标字符串转换成正则，验证是否为之前两个字符串的LCS
function validateLCS(el, str1, str2){
 var re = new RegExp( el.split("").join(".*") )
 console.log(el, re.test(str1),re.test(str2))
 return re.test(str1) && re.test(str2)
}

Utilisation :

function LCS(str1, str2){
 var m = str1.length 
 var n = str2.length
 //....略，自行补充
 var s = printLCS(dp, str1, str2, m, n)
 validateLCS(s, str1, str2)
 return dp[m][n]
}
var c1 = LCS( "ABCBDAB","BDCABA");
console.log(c1) //4 BCBA、BCAB、BDAB
var c2 = LCS("13456778" , "357486782" );
console.log(c2) //5 34678 
var c3 = LCS("ACCGGTCGAGTGCGCGGAAGCCGGCCGAA" ,"GTCGTTCGGAATGCCGTTGCTCTGTAAA" );
console.log(c3) //20 GTCGTCGGAAGCCGGCCGAA

Imprimer tous les LCS

L'idée est similaire à celle ci-dessus. Notons qu'il existe une valeur Math.max dans la méthode LCS. Celle-ci intègre en fait trois situations, donc trois chaînes peuvent être bifurquées. Notre méthode renverra un objet de collection es6 pour une suppression automatique. Puis à chaque fois le nouvel ensemble est utilisé pour fusionner les chaînes de l’ancien ensemble.

//by 司徒正美 打印所有LCS
function printAllLCS(dp, str1, str2, i, j){
 if (i == 0 || j == 0){
  return new Set([""])
 }else if(str1[i-1] == str2[j-1]){
  var newSet = new Set()
  printAllLCS(dp, str1, str2, i-1, j-1).forEach(function(el){
   newSet.add(el + str1[i-1])
  })
  return newSet
 }else{
  var set = new Set()
  if (dp[i][j-1] >= dp[i-1][j]){
   printAllLCS(dp, str1, str2, i, j-1).forEach(function(el){
    set.add(el)
   })
  }
  if (dp[i-1][j] >= dp[i][j-1]){//必须用>=，不能简单一个else搞定
   printAllLCS(dp, str1, str2, i-1, j).forEach(function(el){
    set.add(el)
   })
  } 
  return set
 } 
 }

Utilisation :

function LCS(str1, str2){
 var m = str1.length 
 var n = str2.length
 //....略，自行补充
 var s = printAllLCS(dp, str1, str2, m, n)
 console.log(s)
 s.forEach(function(el){
  validateLCS(el,str1, str2)
  console.log("输出LCS",el)
 })
 return dp[m][n]
}
var c1 = LCS( "ABCBDAB","BDCABA");
console.log(c1) //4 BCBA、BCAB、BDAB
var c2 = LCS("13456778" , "357486782" );
console.log(c2) //5 34678 
var c3 = LCS("ACCGGTCGAGTGCGCGGAAGCCGGCCGAA" ,"GTCGTTCGGAATGCCGTTGCTCTGTAAA" );
console.log(c3) //20 GTCGTCGGAAGCCGGCCGAA

Optimisation de l'espace

Utilisation Tableau roulant :

function LCS(str1, str2){
 var m = str1.length 
 var n = str2.length
 var dp = [new Array(n+1).fill(0)],now = 1，row //第一行全是0
 for(var i = 1; i <= m; i++){ //一共有2行
  row = dp[now] = [0] //第一列全是0
  for(var j = 1; j <= n; j++){//一共有n+1列
   if(str1[i-1] === str2[j-1]){ 
    //注意这里，str1的第一个字符是在第二列中，因此要减1，str2同理
    dp[now][j] = dp[i-now][j-1] + 1 //对角＋1
   } else {
    dp[now][j] = Math.max( dp[i-now][j], dp[now][j-1]) 
   }
  }
  now = 1- now; //1-1=>0;1-0=>1; 1-1=>0 ...
 } 
 return row ? row[n]: 0
}

Solution récursive dangereuse

Une sous-séquence de str1 correspond à la séquence d'indice {1, 2, … , a sous-séquence de m}. Par conséquent, str1 a un total de ${2^m}$ différentes sous-séquences (il en va de même pour str2, comme ${2^n}$), donc la complexité atteint un temps exponentiel étonnant ($ { 2^m * 2^n}$).

//警告，字符串的长度一大就会爆栈
function LCS(str1, str2, a, b) {
  if(a === void 0){
   a = str1.length - 1
  }
  if(b === void 0){
   b = str2.length - 1
  }
  if(a == -1 || b == -1){
   return 0
  } 
  if(str1[a] == str2[b]) {
   return LCS(str1, str2, a-1, b-1)+1;
  }
  if(str1[a] != str2[b]) {
   var x = LCS(str1, str2, a, b-1)
   var y = LCS(str1, str2, a-1, b)
   return x >= y ? x : y
  }
 }

J'ai compilé ce qui précède pour vous, j'espère que cela vous sera utile à l'avenir.

Articles connexes :

Utilisation de vue pour implémenter la méthode de définition d'itinéraire secondaire

Développement de projet React

Une variété d'implémentations de routage dans Vue-Router2.X

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!