10

Como comparar a string com o array e retornar o que tiver mais palavras compatíveis?

Exemplo:

string = "uma frase qualquer aqui"
array = ["frase qualquer", "uma qualquer aqui", "nada compatível"]

Retorna o segundo item do array por ter 3 palavras compatíveis


Tentei usar includes() mas ele retorna o primeiro item por ter ao menos 1 palavra compatível

//string a ser comparada com o array
let str = "uma frase qualquer aqui";
let strArr = str.split(" ");
//ao comparar com o array deve retornar o segundo item, pois tem mais palavras compativeis
let arr = ["frase qualquer", "uma qualquer aqui", "nada compatível"];

function maisCompativel(){
  for(let i = 0; i < strArr.length; i++){
    if(arr.includes(strArr[i])){
      //retornar o item mais compativel / mais parecido
    }
  }
}

4 Respostas 4

13

O problema é que você precisa dividir cada elemento de arr em um array de palavras. Por exemplo:

["frase qualquer", "uma qualquer aqui", "nada compatível"]

Tem que ser transformado em:

[
  ["frase", "qualquer"],
  ["uma", "qualquer", "aqui"],
  ["nada", "compatível"]
]

Para que você possa comparar cada palavra desse array de arrays individualmente.


Como primeira tentativa, você pode chegar em uma solução mais ou menos assim:

function mostCompatible(string, array) {
  const words = string.split(' ');

  // O `array` atualmente contém diversas strings.
  // Fazendo o `map` abaixo, fazemos que cada string desse array
  // seja dividida pelo espaço. Desse modo, teremos um array de arrays.
  const subArrays = array.map((subString) => subString.split(' '));

  // Na variável a seguir, vamos armazenar o índice referente
  // ao elemento que tiver mais "palavras compatíveis", e o
  // número de palavras compatíveis encontradas:
  let current = {
    index: null,
    compatibleWordsCount: 0
  };

  // Agora vamos verificar qual elemento de `subArrays` tem
  // mais "palavras compatíveis". Estou utilizando o `entries`
  // como forma de obter o índice e o valor no laço `for..of`.
  for (const [index, subArray] of subArrays.entries()) {
    // Vamos obter a quantidade de "elementos compatíveis".
    // Note que a seguinte computação possui complexidade `O(n^2)`.
    const compatibleWordsCount = words.filter((word) => subArray.includes(word))
      .length;

    // Caso a quantidade de elementos compatíveis seja maior que o da iteração
    // anterior, vamos sobrescrever o objeto `current`.
    if (compatibleWordsCount > current.compatibleWordsCount) {
      current = { index, compatibleWordsCount };
    }
  }

  // Retornar o elemento de `array` correspondente ao índice do `subArray` com
  // mais "elementos compatíveis" encontrados.
  return array[current.index];
}

console.log(
  mostCompatible('uma frase qualquer aqui', [
    'frase qualquer',
    'uma qualquer aqui',
    'nada compatível'
  ])
); // Deve logar `'uma qualquer aqui'`.

O problema é que ela não é muito performática, tendo complexidade de aproximadamente O(n3), já que estamos utilizando um includes dentro de um filter, que está dentro de um for, e cada uma dessas etapas possui complexidade O(n). Mas, francamente, você só precisa levar isso em consideração se for levar um número significativo de dados para essa função.

Uma implementação um pouco mais eficiente poderia fazer uso de um mapa para realizar as buscas. Assim, você reduz a complexidade de cada busca de O(n) para O(1). Algo assim:

function createCountMap(arr) {
  const map = Object.create(null);
  for (const item of arr) {
    map[item] = (map[item] || 0) + 1;
  }
  return map;
}

function mostCompatible(string, array) {
  // Criamos um mapa com cada palavra a ser procurda.
  // Assim, a busca terá complexidade O(1) ao invés de O(n).
  const wordsMap = createCountMap(string.split(' '));

  let result = {
    index: null,
    compatibleWordsCount: 0
  };

  for (let index = 0; index < array.length; index++) {
    const currentString = array[index];
    let compatibleWordsCount = 0;

    for (const word of currentString.split(' ')) {
      if (wordsMap[word]) {
        compatibleWordsCount++;
      }
    }

    if (compatibleWordsCount > result.compatibleWordsCount) {
      result = { index, compatibleWordsCount };
    }
  }

  return array[result.index];
}

console.log(
  mostCompatible('uma frase qualquer aqui', [
    'frase qualquer',
    'uma qualquer aqui',
    'nada compatível'
  ])
); // Deve logar `'uma qualquer aqui'`.

Para saber mais sobre essa notação – O(n) – que eu utilizei, leia aqui.

1
  • Mas se o array em que vai ser procurado for fixo, pode guardar o resultado do map e ele só será usado uma vez, ou até nenhuma
    – Costamilam
    Commented 6/01/2020 às 22:39
6

Uma forma é usando dois .forEach(): o primeiro na array com as frases e o segundo aninhado na array da string. Aí vai contando o que tem mais ocorrências e compara com uma variável que armazena o número de maior ocorrência, e outra variável para armazenar em qual índice da array teve mais ocorrências:

let str = "uma frase qualquer aqui";
let strArr = str.split(" ");
let arr = ["frase qualquer", "uma qualquer aqui", "nada compatível"];

function maisCompativel(str){
   let indice,
       maior = 0;
   arr.forEach((a,i)=>{
      let conta = 0;
      strArr.forEach(b=>{
         if(a.includes(b)) conta++;
      });

      if(conta > maior){
         indice = i;
         maior = conta;
      }
  });
  return `O que tem mais ocorrência é o índice [${indice}] com ${maior} palavras: "${arr[indice]}"`;
}

console.log(maisCompativel());

0
6

Opto aqui por mostrar outra abordagem ao mesmo problema, e aproveitando quase todo o código que você já tinha.

A diferença é que este utiliza um vetor auxiliar de contagens para cada uma das frases, que contabiliza quantas palavras tem em comum. Este vetor vai sendo preenchido à medida que percorre a frase de entrada por palavra, tal como já tem no seu código.

Exemplo:

//string a ser comparada com o array
let str = "uma frase qualquer aqui";
let strArr = str.split(" ");
//ao comparar com o array deve retornar o segundo item, pois tem mais palavras compativeis
let arr = ["frase qualquer", "uma qualquer aqui", "nada compatível"];

function maisCompativel(){
  //Vetor de contagens com tamanho de arr e preenchido com zeros
  const contagens = new Array(arr.length).fill(0); 
  
  for(let i = 0; i < strArr.length; i++){
  
    //loop para percorrer as frases 
    for (let j = 0; j < arr.length; j++){ 
      if (arr[j].includes(strArr[i])){
        contagens[j]++; //contabilizar a palavra já que existe
      }
    }
  }
  
  let maiorContagem = Math.max(...contagens);
  let posicaoMaior = contagens.indexOf(maiorContagem);
  return arr[posicaoMaior];
}

console.log(maisCompativel());

Se comparar o meu código com o seu, vê que no percorrer das palavras apenas tem mais um for. Tem também a lógica dentro do if para a contabilização, que estava em falta.

2
  • Não tenho certeza, mas acho que o if pode ser simplificado para contagens[j] += arr[j].includes(strArr[i]) que vai adicionar 0 ou 1 respectivamente para true ou false
    – Costamilam
    Commented 6/01/2020 às 22:44
  • @Costamilam De facto pode, mas prefiro assim que é mais legível. De qualquer forma agradeço o comentário.
    – Isac
    Commented 7/01/2020 às 0:53
-2

Pode utilizar uma implementação do similar_text do PHP em JS Exemplo

Ai faz um loop e retorna o item que tiver o maior score.

//string a ser comparada com o array
let str = "uma frase qualquer aqui";
//ao comparar com o array deve retornar o segundo item, pois tem mais palavras compativeis
let arr = ["frase qualquer", "uma qualquer aqui", "nada compatível"];

var max = 0;
var id = 0;

function maisCompativel() {
  for (let i = 0; i < arr.length; i++) {
    value = similar_text(str, arr[i]);
    if (value > max) {
      max = value
      id = i;
    }

  }
  return arr[id];
}

function similar_text(first, second, percent) { // eslint-disable-line camelcase
  //  discuss at: https://locutus.io/php/similar_text/
  // original by: Rafał Kukawski (https://blog.kukawski.pl)
  // bugfixed by: Chris McMacken
  // bugfixed by: Jarkko Rantavuori original by findings in stackoverflow (https://stackoverflow.com/questions/14136349/how-does-similar-text-work)
  // improved by: Markus Padourek (taken from https://www.kevinhq.com/2012/06/php-similartext-function-in-javascript_16.html)
  //   example 1: similar_text('Hello World!', 'Hello locutus!')
  //   returns 1: 8
  //   example 2: similar_text('Hello World!', null)
  //   returns 2: 0

  if (first === null ||
    second === null ||
    typeof first === 'undefined' ||
    typeof second === 'undefined') {
    return 0
  }

  first += ''
  second += ''

  var pos1 = 0
  var pos2 = 0
  var max = 0
  var firstLength = first.length
  var secondLength = second.length
  var p
  var q
  var l
  var sum

  for (p = 0; p < firstLength; p++) {
    for (q = 0; q < secondLength; q++) {
      for (l = 0;
        (p + l < firstLength) && (q + l < secondLength) && (first.charAt(p + l) === second.charAt(q + l)); l++) { // eslint-disable-line max-len
        // @todo: ^-- break up this crazy for loop and put the logic in its body
      }
      if (l > max) {
        max = l
        pos1 = p
        pos2 = q
      }
    }
  }

  sum = max

  if (sum) {
    if (pos1 && pos2) {
      sum += similar_text(first.substr(0, pos1), second.substr(0, pos2))
    }

    if ((pos1 + max < firstLength) && (pos2 + max < secondLength)) {
      sum += similar_text(
        first.substr(pos1 + max, firstLength - pos1 - max),
        second.substr(pos2 + max,
          secondLength - pos2 - max))
    }
  }

  if (!percent) {
    return sum
  }

  return (sum * 200) / (firstLength + secondLength)
}

console.log(maisCompativel());

9
  • 1
    Embora este link possa responder à pergunta, é melhor incluir as partes essenciais da resposta aqui e fornecer o link para referência. As respostas apenas por link podem ser invalidadas se a página com o link for alterada. - Da Revisão
    – DaviAragao
    Commented 6/01/2020 às 18:22
  • @DaviAragao Adicionado código a resposta. Porém não entendo pq se eu responder o algorítimo é uma resposta válida, porém se coloco um link com exemplo se forna inválido.
    – Fabricio
    Commented 6/01/2020 às 19:06
  • 3
    Sugiro que leia o FAQ: Queremos respostas que contenham somente links?
    – hkotsubo
    Commented 6/01/2020 às 19:15
  • @hkotsubo Por isso que minha resposta era o que ele deveria fazer. "Utilizar uma implementação do similar_text" + "Loop com a verificação do score". Minha resposta nunca teve o intuito de postar o código ou de fazer todo trabalho. Se sempre receber as coisas na mão nunca irá aprender. A função similar_text é bem difundida e com um google por "similar_text source code" retorna a sua implementação. Passei um link para ajudar, como um complemento da resposta. O FAQ mencionado diz que isso é ótimo e deve ser utilizado assim. Porém, pelo visto, o que é falado no FAQ só é valido se não for um código
    – Fabricio
    Commented 6/01/2020 às 20:10
  • 1
    Há uma diferença entre dar o código de mão beijada e dar o código explicando como e porque ele funciona. A primeira forma não é bem aceita pq de fato a pessoa não aprende, a segunda forma é preferível porque aí a resposta fica completa, sem depender de links externos (aliás, esse é o ponto principal de não colocar apenas um link: que toda a informação fique no próprio Stack Overflow). Se for pra dizer apenas "use o algoritmo X deste link" e mais nada, faça nos comentários. Se for responder, que o faça da forma mais completa possível.
    – hkotsubo
    Commented 6/01/2020 às 20:22

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .