¿Cuál es la forma más rápida de verificar si una palabra de una cadena está en otra cadena?

Question

Tengo una cadena de palabras; llamémosles bad:

bad = "foo bar baz" 

puedo mantener esta cadena como una cadena de espacios en blanco separado, o como una lista:

bad = bad.split(" "); 

Si tengo otra cadena, así:

str = "This is my first foo string" 

¿Cuál es la forma rápida de verificar si alguna palabra de la cadena bad está dentro de mi cadena de comparación, y cuál es la forma más rápida de hacerlo? para eliminar dicha palabra si se encuentra?

#Find if a word is there 
bad.split(" ").each do |word| 
    found = str.include?(word) 
end 

#Remove the word 
bad.split(" ").each do |word| 
    str.gsub!(/#{word}/, "") 
end 

Answer 1

Si la lista de malas palabras se pone enorme, un hash es mucho más rápido:

require 'benchmark' 

    bad = ('aaa'..'zzz').to_a # 17576 words 
    str= "What's the fasted way to check if any word from the bad string is within my " 
    str += "comparison string, and what's the fastest way to remove said word if it's " 
    str += "found" 
    str *= 10 

    badex = /\b(#{bad.join('|')})\b/i 

    bad_hash = {} 
    bad.each{|w| bad_hash[w] = true} 

    n = 10 
    Benchmark.bm(10) do |x| 

     x.report('regex:') {n.times do 
     str.gsub(badex,'').squeeze(' ') 
     end} 

     x.report('hash:') {n.times do 
     str.gsub(/\b\w+\b/){|word| bad_hash[word] ? '': word}.squeeze(' ') 
     end} 

    end 
       user  system  total  real 
regex:  10.485000 0.000000 10.485000 (13.312500) 
hash:  0.000000 0.000000 0.000000 ( 0.000000) 

Answer 2

mala = "foo bar baz"

=> "foo bar baz"

cadena = "Esta es mi primera cadena foo"

=> "Esta es mi primera cadena foo"

(str.split (' ') - bad.split (' ')) join ('')

.

=> "Esta es mi primera cadena"

Answer 3

por lo general hacen un punto de no optimizar sin mediciones, pero aquí hay un WAG:

Para que sea más rápido, que debe recorrer cada cadena una vez. Desea evitar un ciclo con un recuento incorrecto * comparaciones internas. Entonces, podrías construir una gran expresión regular y un gsub con ella.

(foo añadiendo variantes para probar la palabra obras de contorno)

str = "This is my first foo fooo ofoo string" 

=> "This is my first foo fooo ofoo string" 

badex = /\b(#{bad.split.join('|')})\b/ 

=> /\b(foo|bar|baz)\b/ 

str.gsub(badex,'').gsub(' ',' ') 

=> "This is my first fooo ofoo string" 

Por supuesto, la gran expresión regular resultante podría ser tan lento como la iteración anidada implícita en mi otra respuesta. La única forma de saber es medir.

Answer 4

Incluido? método es lo que necesitas. La especificación de Ruby String dice:

str.include? (Cadena) -> verdadero o falso Devuelve verdadero si str contiene la cadena o el carácter dados.

"hello" .include? "lo" -> verdadero

"hello" .include? "ol" -> falso

"hello" .include? ? H -> true

Nota que tiene O (n) y lo que se propuso es O (n^2)

Answer 5

Todas las soluciones tienen problemas al agarrar las malas palabras, si el caso no coincide.La solución de expresiones regulares es más fácil de solucionar mediante la adición de la ignore-caja de la bandera:

 
badex = /\b(#{bad.split.join('|')})\b/i 

Además, el uso de "String".include?(" String ") dará lugar a problemas de límites con las primeras y últimas palabras en la cadena o cadenas donde las palabras de destino tienen puntuacion o tienen guiones Las pruebas para esas situaciones resultarán en la necesidad de muchos otros códigos. Por eso, creo que la solución de expresiones regulares es la mejor. No es el más rápido, pero va a ser más flexible desde el primer momento y, si los otros algoritmos se ajustan para manejar el plegado de casos y las palabras compuestas, la solución de expresiones regulares podría avanzar.

 
#!/usr/bin/ruby 

require 'benchmark' 

bad = 'foo bar baz comparison' 
badex = /\b(#{bad.split.join('|')})\b/i 
str = "What's the fasted way to check if any word from the bad string is within my comparison string, and what's the fastest way to remove said word if it's found?" * 10 

n = 10_000 
Benchmark.bm(20) do |x| 
    x.report('regex:') do 
    n.times { str.gsub(badex,'').gsub(' ',' ') } 
    end 

    x.report('regex with squeeze:') do 
    n.times{ str.gsub(badex,'').squeeze(' ') } 
    end 

    x.report('array subtraction') do 
    n.times { (str.split(' ') - bad.split(' ')).join(' ') } 
    end 
end 

Hice la variable str mucho más tiempo, para hacer que las rutinas trabajen un poco más.

 
          user  system  total  real 
regex:    0.740000 0.010000 0.750000 ( 0.752846) 
regex with squeeze: 0.570000 0.000000 0.570000 ( 0.581304) 
array subtraction  1.430000 0.010000 1.440000 ( 1.449578) 

Doh !, estoy demasiado acostumbrado a cómo otros idiomas manejan sus puntos de referencia. ¡Ahora lo tengo funcionando y me veo mejor!

Solo un pequeño comentario sobre lo que parece que el OP está tratando de hacer: la eliminación de palabras en la lista negra es fácil de engañar, y un esfuerzo por mantener. L33t-sp34k hace que sea trivial escuchar las palabras a través de. Dependiendo de la aplicación, la gente lo considerará un juego para encontrar formas de empujar palabras ofensivas después del filtrado. La mejor solución que encontré cuando me pidieron que trabajara en esto, fue crear un generador que creara todas las variaciones en una palabra y las volcara en una base de datos donde algún proceso podría verificar tan pronto como sea posible, en lugar de hacerlo en tiempo real. Se pueden demorar un millón de cadenas pequeñas si estás buscando en una larga lista de palabras ofensivas; Estoy seguro de que podríamos llegar a una lista bastante completa de cosas que alguien consideraría ofensivas, pero eso es un ejercicio para otro día.

No he visto nada similar en Ruby to Perl's Regexp::Assemble, pero esa era una buena forma de resolver este tipo de problema. Puede pasar una serie de palabras, más opciones para plegar mayúsculas y minúsculas, y escupirá un patrón de expresiones regulares que coincidirá con todas las palabras, y se considera que sus características comunes dan como resultado el patrón más pequeño que coincidirá con todas las palabras de la lista. El problema después de eso es ubicar qué palabra en la cadena original coincide con los hits encontrados por el patrón, para que puedan ser eliminados. Las diferencias en palabras en mayúsculas y aciertos dentro de palabras compuestas hacen que el reemplazo sea más interesante.

Y ni siquiera entraremos en palabras que sean benignas u ofensivas según el contexto.

---

he añadido un bit de prueba más completa del índice de referencia matriz de resta, para adaptarse a la forma en que tendría que trabajar en una verdadera pieza de código. La cláusula if se especifica en la respuesta, esto ahora lo refleja:

#!/usr/bin/env ruby 

require 'benchmark' 

bad = 'foo bar baz comparison' 
badex = /\b(#{bad.split.join('|')})\b/i 
str = "What's the fasted way to check if any word from the bad string is within my comparison string, and what's the fastest way to remove said word if it's found?" * 10 

str_split = str.split 
bad_split = bad.split 

n = 10_000 
Benchmark.bm(20) do |x| 
    x.report('regex') do 
    n.times { str.gsub(badex,'').gsub(' ',' ') } 
    end 

    x.report('regex with squeeze') do 
    n.times{ str.gsub(badex,'').squeeze(' ') } 
    end 

    x.report('bad.any?') do 
    n.times { 
     if (bad_split.any? { |bw| str.include?(bw) }) 
     (str_split - bad_split).join(' ') 
     end 
    } 
    end 

    x.report('array subtraction') do 
    n.times { (str_split - bad_split).join(' ') } 
    end 

end 

con dos pruebas:

ruby test.rb 
          user  system  total  real 
regex     1.000000 0.010000 1.010000 ( 1.001093) 
regex with squeeze 0.870000 0.000000 0.870000 ( 0.873224) 
bad.any?    1.760000 0.000000 1.760000 ( 1.762195) 
array subtraction  1.350000 0.000000 1.350000 ( 1.346043) 

ruby test.rb 
          user  system  total  real 
regex     1.000000 0.010000 1.010000 ( 1.004365) 
regex with squeeze 0.870000 0.000000 0.870000 ( 0.868525) 
bad.any?    1.770000 0.000000 1.770000 ( 1.775567) 
array subtraction  1.360000 0.000000 1.360000 ( 1.359100) 

Answer 6

bad = %w(foo bar baz) 
str = "This is my first foo string" 

# find the first word in the list 
found = bad.find {|word| str.include?(word)} 

# remove it 
str[found] = '' ;# str => "This is my first string" 

Answer 7

que había referencia esta:

bad = "foo bar baz".split(' ') 
str = "This is my first foo string".split(' ') 

# 1. What's the fasted way to check if any word from the bad string is within my comparison string 
p bad.any? { |bw| str.include?(bw) } 

# 2. What's the fastest way to remove said word if it's found? 
p (str - bad).join(' ') 

any? se comprobará rápidamente tan pronto como vea una coincidencia. Si puede ordenar sus palabras malas según su probabilidad, puede guardar algunos ciclos.

Answer 8

Aquí hay uno que buscará palabras y frases.

def checkContent(str) 
    bad = ["foo", "bar", "this place sucks", "or whatever"] 

    # may be best to map and singularize everything as well. 
    # maybe add some regex to catch those pesky, "How i make $69 dollars each second online..." 
    # maybe apply some comparison stuff to check for weird characters in those pesky, "How i m4ke $69 $ollars an hour" 


    bad_hash = {} 
    bad_phrase_hash = {} 

    bad.map(&:downcase).each do |word| 
     words = word.split().map(&:downcase) 
     if words.length > 1 
      words.each do |inner| 
       if bad_hash.key?(inner) 
        if bad_hash[inner].is_a?(Hash) && !bad_hash[inner].key?(words.length) 
         bad_hash[inner][words.length] = true 
        elsif bad_hash[inner] === 1 
         bad_hash[inner] = {1=>true,words.length => true} 
        end 
       else 
        bad_hash[inner] = {words.length => true} 
       end 
      end 
      bad_phrase_hash[word] = true 
     else 
      bad_hash[word] = 1 
     end 
    end 

    string = str.split().map(&:downcase) 
    string.each_with_index do |word,index| 
     if bad_hash.key?(word) 
      if bad_hash[word].is_a?(Hash) 
       if bad_hash[word].key?(1) 
        return false 
       else 
        bad_hash[word].keys.sort.each do |length| 
         value = string[index...(index + length)].join(" ") 
         if bad_phrase_hash.key?(value) 
          return false 
         end 
        end 
       end 
      else 
       return false 
      end 
     end 
    end 
    return true 
    end