Какой самый быстрый способ проверить, находится ли слово из одной строки в другой строке?

Question

У меня есть строка слов; давайте назовем их bad:

bad = "foo bar baz"

Я могу сохранить эту строку в виде строки, разделенной пробелами, или в виде списка:

bad = bad.split(" ");

Если у меня есть другая строка, например:

str = "This is my first foo string"

Какой самый быстрый способ проверить, находится ли какое-либо слово из строки bad в моей строке сравнения, и Какой самый быстрый способ удалить это слово, если оно найдено?

#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

Если список плохих слов становится огромным, хеш намного быстрее:

    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

bad = "foo bar baz"

=> "foo bar baz"

str = "Это моя первая строка foo"

=> "Это моя первая строка foo"

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

=> "Это моя первая строка"

Answer 3

Все решения имеют проблемы с ловлей плохих слов, если регистр не совпадает. Решение regex проще всего исправить, добавив флаг ignore-case:

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

Кроме того, использование "String".include?(" String ") приведет к граничным проблемам с первым и последним словами в строке или строками, где целевые слова имеют знаки препинания или дефисы. Тестирование в таких ситуациях приведет к тому, что потребуется много другого кода. Поэтому я думаю, что решение регулярных выражений является лучшим. Это не самый быстрый, но он будет более гибким прямо из коробки, и, если другие алгоритмы будут настроены для обработки свертывания и составных слов, решение regex может вырваться вперед.

#!/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

Я сделал переменную str намного длиннее, чтобы подпрограммы работали немного сложнее.

                          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)

Дох! Я слишком привык к тому, как другие языки справляются со своими тестами. Теперь у меня все работает и выглядит лучше!

Просто небольшой комментарий о том, что, по-видимому, пытается сделать ФП: удаление слов из черного списка легко обмануть, и боль, которую нужно поддерживать. L33t-sp34k упрощает просмотр слов. В зависимости от приложения, люди считают это игрой, чтобы найти способы отодвинуть оскорбительные слова за пределы фильтрации. Лучшее решение, которое я нашел, когда меня попросили поработать над этим, состояло в том, чтобы создать генератор, который бы создавал все варианты слова и помещал их в базу данных, где какой-то процесс мог проверить как можно скорее, а не в режиме реального времени. Проверка миллионов маленьких строк может занять некоторое время, если вы ищете длинный список оскорбительных слов; Я уверен, что мы могли бы придумать целый список вещей, которые кто-то посчитал бы оскорбительными, но это упражнение для другого дня.

Я не видел в Ruby ничего похожего на Perl Regexp :: Assemble , но это был хороший способ справиться с подобной проблемой. Вы можете передать массив слов, а также опции для свертывания и границ слов, и он будет выдавать шаблон регулярного выражения, который будет соответствовать всем словам, с их общностью, которая, как считается, приведет к наименьшему шаблону, который будет соответствовать всем словам в список. После этого возникает проблема с поиском того, какое слово в исходной строке соответствует совпадениям, найденным шаблоном, чтобы их можно было удалить. Различия в регистре слов и совпадениях в сложных словах делают эту замену более интересной.

И мы даже не будем вдаваться в слова, которые являются мягкими или оскорбительными в зависимости от контекста.

---

Я добавил немного более всеобъемлющий тест для теста вычитания массива, чтобы соответствовать тому, как он должен работать в реальном куске кода. В ответе указано предложение if, теперь оно отражает его:

#!/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

с двумя тестовыми прогонами:

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 4

Вот тот, который будет проверять слова и фразы.

 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

Answer 5

Я бы проверил это:

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(' ')

любой? проведет быструю проверку, как только увидит совпадение. Если вы можете упорядочить свои плохие слова по вероятности, вы можете сохранить несколько циклов.

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

Включать? метод это то, что вам нужно. Рубиновая спецификация гласит:

str.include? (Строка) -> true или false Возвращает true, если str содержит данную строку или символ.

"привет" .include? "lo" -> true

"привет" .include? "ol" -> false

"привет" .include? ? h -> правда

Обратите внимание, что у него есть O (n), а вы задали O (n ^ 2)

Answer 8

Я обычно не оптимизирую без измерений, но вот что-то вроде:

Чтобы сделать это быстро, вы должны пройти по каждой строке один раз. Вы хотите избежать цикла с плохим счетчиком * str count внутренних сравнений. Таким образом, вы можете создать большое регулярное выражение и gsub с ним.

(добавление вариантов foo для проверки границ слов)

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"

Конечно, огромное полученное регулярное выражение может быть таким же медленным, как подразумеваемая вложенная итерация в моем другом ответе. Единственный способ узнать это измерить.