Удалить строки, содержащие подряд (или не подряд) три и более любые цифры (буквы)

#linux #perl #sed #grep #awk

Вопрос разбивается на несколько похожих, дабы не создавать каждый раз отдельно.
Используемые символы в строках: все цифры, все строчные и заглавные буквы английского
алфавита. Строки вида:

a22tbf645
92STbfF4W
92rtRe7Ev
gyue73Pr4
u8t9D03gE
a2t4TA6Kk
Lj3D2Jrs1


желаемый ответ после применения одновременно всего указанного ниже: Lj3D2Jrs1

1.a Удалить строки, содержащие на любых позициях три или более любые разные цифры,
идущие подряд.

1.b Удалить строки, содержащие на любых позициях три или более любые строчные буквы,
идущие подряд.

1.с Удалить строки, содержащие на любых позициях три или более любые заглавные буквы,
идущие подряд.

2.a Удалить строки, содержащие на любых позициях четыре или более любые цифры вообще
в строке.

2.b Удалить строки, содержащие на любых позициях четыре или более любые строчные
буквы вообще в строке.

2.c Удалить строки, содержащие  четыре или более любые заглавные буквы вообще в строке.


Удалить строки, содержащие на любых позициях одинаковые буквы подряд в разных регистрах,
например aA Aa


Можно ли объединить все эти условия в одну команду?
Предпочтительно sed, awk, grep, tr, cut, perl, python, может что-то еще - упор на
скорость обработки- большие массивы.(чем кстати побыстрее?)
спасибо
    

Ответы

Ответ 1

Решение с использованием простой машины состояний (детерминированного конечного автомата)
было написано "в лоб" на Delphi, затем я его, как сумел, почти напрямую перевёл на
Python, так что код громоздкий, явно не pythonic и производительность может страдать
оттого, что я не использую какие-то встроенные штучки и не особо знаю, что влияет на
производительность Python. Например, время сократилось с 41 до 33 секунд, когда я заменил
выделение символа

        for i in range(len(line)):
            ch = line[i]


на 

        for ch in line:


Для файла из 10 миллионов строк по 9 случайных символов (110 мегабайт), принадлежащих
указанным множествам, нативный (Delphi) код под Windows на Celeron 2.8 ГГц затрачивает
около 4-5 секунд (3-4 секунды на загрузку данных с HDD и около секунды на саму обработку).
Данный код (Python 3.6) тратит на всё 33 секунды (из них 11 сек. на загрузку файла,
если просто прочитать все строки и ничего не делать).

Код проходит по каждой строке, считая количество больших, малых букв и цифр и прерывает
обработку строки, если какой-либо из счётчиков превышает предел (3) (условия 2).

state  - это текущее состояние, обозначает, какого типа символ обрабатывался ранее.
0 - неопределённо, 1 - цифра, 2 - заглавная, 3 - маленькая буква.

Если state не меняется, то проверяется длина серии seriescount из символов текущего
типа (условия 1)

Если state меняется с 2 на 3 или наоборот, то проверяется, не был ли прошлый символ
копией текущего в другом регистре (условие 3).

def dellines():
    infile = open("d:\m1.txt", "r")
    outfile = open("d:\m2.txt", "w")

    for line in infile:
        seriescnt = 0
        bigcnt = 0
        smallcnt = 0
        digitcnt = 0
        state = 0
        for ch in line:

            if (ch >= "0") and (ch <= "9"):

                if (state == 1):
                    seriescnt += 1
                    if (seriescnt > 2):
                        state = 0
                        break
                else:
                  seriescnt = 1

                digitcnt += 1
                if (digitcnt > 3):
                     state = 0
                     break
                state = 1
            elif (ch >= "A") and (ch <= "Z"):

                if (state == 3):
                    if (ord(lastch) == ord(ch) + 32):
                        state = 0
                        break

                if (state == 2):
                    seriescnt += 1
                    if (seriescnt > 2):
                        state = 0
                        break
                else:
                  seriescnt = 1

                bigcnt += 1
                if (bigcnt > 3):
                     state = 0
                     break

                lastch = ch
                state = 2
            elif (ch >= "a") and (ch <= "z"):

                if (state == 2):
                    if (ord(lastch) == ord(ch) - 32):
                        state = 0
                        break

                if (state == 3):
                    seriescnt += 1
                    if (seriescnt > 2):
                        state = 0
                        break
                else:
                  seriescnt = 1

                smallcnt += 1
                if (smallcnt > 3):
                     state = 0
                     break

                lastch = ch
                state = 3

        if (state):
            outfile.write(line)
    outfile.close()
    infile.close()

start = time.time()
dellines()
end = time.time()
print(end - start)


Ответ 2

Вот (вероятно) малоэффективный и откровенно тупой, но рабочий вариант на классических
регулярных выражениях:

grep -v\
 -e '[[:digit:]]\{3,\}'\
 -e '[[:lower:]]\{3,\}'\
 -e '[[:upper:]]\{3,\}'\
 -e '\([[:digit:]].*\)\{4,\}'\
 -e '\([[:lower:]].*\)\{4,\}'\
 -e '\([[:upper:]].*\)\{4,\}'\
 $(for i in {a..z}; do echo "-e $i${i^^} -e ${i^^}$i"; done)


Ответ 3

Версия на Python за основу взяты ответы из СО.

Создаем для примера файл из случайной выборки 100М с заданным патерном из вопроса:
[a-zA-Z0-9]{9}

Характеристики машины:

~$ uname -r; grep -im1 "model name" /proc/cpuinfo
4.17.3-200.fc28.x86_64
model name      : Intel(R) Core(TM) i7-3770S CPU @ 3.10GHz




Исправленный вариант только на регулярных выражениях без выполнения условия 3

~$ cat lines_filter_re.py

#!/usr/bin/env python3
import sys
import re
import fileinput


for line in fileinput.input():
    pat_re = re.compile(r""""
       ([0-9]){3}            # Any 3 sequensial numbers
       |([a-z]){3}           # Any 3 lsequensia lower case letters
       |([A-Z]){3}           # Any 3 sequensia lupper case letters
       |(.*[0-9].*){4}       # any 4 digits in any place
       |(.*[A-Z].*){4}       # any 4 upper case ltters at any place
       |(.*[a-z].*){4}       # any 4 loser case lttters at any place
       """, re.VERBOSE)

    if not pat_re.findall(line):
        sys.stdout.write(line)
# end of script

~$ cat test.txt; echo; ./lines_filter_re.py < test.txt
a22tbf645
92STbfF4W
92rtRe7Ev
gyue73Pr4
u8t9D03gE
a2t4TA6Kk
aAb12cAB1
Lj3D2Jrs1
---------
a2t4TA6Kk
aAb12cAB1
Lj3D2Jrs1

~$ wc -l file_9w_100M
6180836 file_9w_100M

~$ time ./lines_filter_re.py >/dev/null < file_9w_100M
real    1m10.668s
user    1m10.424s
sys     0m0.060s




Метод на Rust, работает x15 раз быстрей:

extern crate regex;

use regex::RegexSet;
use std::io::{stdin, BufRead};

fn main() {
    let set = RegexSet::new(&[
        r"([0-9]){3}",
        r"([a-z]){3}",
        r"([A-Z]){3}",
        r"(.*[0-9].*){4}",
        r"(.*[A-Z].*){4}",
        r"(.*[a-z].*){4}",
    ]).unwrap();

    let stdin = stdin();
    let test_string = "Test me once";

    println!("{}", set.is_match(test_string));

    for line in stdin.lock().lines() {
        let mut line_str = line.unwrap();

        if set.is_match(&mut line_str) {
            continue;
        } else {
            println!("{}", line_str);
        }
    }
}
// End of main.rs


Тесты

~$ time ./lfr  < ../../../../Python/test.txt
true
a2t4TA6Kk
aAb12cAB1
Lj3D2Jrs1
real    0m0.004s
user    0m0.002s
sys     0m0.002s

~$ time ./lfr >/dev/null < ../../../../Python/file_9w_100M
real    0m2.934s
user    0m2.866s
sys     0m0.062s


Ссылки


https://stackoverflow.com/questions/34443946
Как вырезать только строки, которые не имеют повторяющихся символов (cut/sed/awk)
или Python?

Найти отстутствующий в последовательности номер

#linux #bash #perl #sed #awk

После работы некоторого скрипта, в файл записывается примерно следующее:

1 ---> something
2 ---> something
3 ---> something
...
18254 --> something


Бывает такое, что в виду того, что я использую в скрипте старый добрый eval, который
помогает мне, чтобы прога не упала на какой-либо ошибке, то какой-нибудь запрос (пусть
это будет 4205) может не записаться в файл:

Покажу на примере:

...
4200 ---> something
4201 ---> something
4202 ---> something
4203 ---> something
4204 ---> something
4206 ---> something


Вопрос: как проверить, какого номера строки (или просто, какого номера нет в файле)
нет в файле? И возможно ли?
    

Ответы

Ответ 1

Можно сделать как-то так:

awk -v var="$((`head -n 1 file | awk '{print $1}'`))" 'BEGIN {p=var} {for(i=p+1;
i<$1; i++) print i} {p=$1}' file


Результат будет:

4205



Сначала мы забираем первое число, которое у нас есть в файле. Если этого не делать,
то счет будет с 1. Просто у вас из вопроса не ясно, с какого числа начинается счет.
Потом через awk мы просто проверяем последовательность чисел. И если числа нет, то
выводим его на экран.


Для случая, если ВСЕГДА последовательность чисел начинается с 1

awk '{for(i=p+1; i<$1; i++) print i} {p=$1}' file


Ответ 2

seq $(grep -oP '^\d+' input.txt | tail -1) | diff - <(grep -oP '^\d+' input.txt)
| grep '<'



Сперва находим последнюю пронумерованную строку (grep -oP '^\d+' input.txt | tail -1)
Далее создаем последовательность без потери чисел (seq см.предыдущее)
Сравниваем полученную последовательность с той, что имеется в файле (см. предыдущее
| diff - <(grep -oP '^\d+' input.txt)
Выводим отсутствующие числа (см. предыдущее | grep '<')


Команду grep -oP '^\d+' input.txt можно вывести в переменную, чтобы не тратиться
на повторное чтение данных из файла.
В случае поиска отсутствия диапазонов чисел лучше использовать awk.

Дополнение

# заносим номера строк в переменную
n=($(grep -oP '^\d+' input.txt))
# выводим различия целочисленных последовательностей
echo $(seq ${n[-1]}) ${n[@]} | tr ' ' '\n' | sort -n | uniq -u

Поиск повторяющихся строк

#python #grep #perl #awk #linux

Привет.
Возник вопрос:
Есть файл 1 ~ 2GB 
и есть файл 2 ~ 1MB
Вопрос - как наиболее быстро подсчитать кол-во вхождений строк из файла2 в файле1?
К примеру файл1:
Тест корова большая
Флагман большая корова
Трубадур золотистый
Флагманский телефон N90
Логическое оформление Тест корова
Бла бла стар

Файл2:
Трубадур
Тест корова
телефон

Должно получиться:
Трубадур 1
Тест корова 2
телефон 1

Файл 1 много больше файл2.    

Ответы

Ответ 1

Эффективным методом поиска нескольких подстрок одновременно в большом тексте является
алгоритм Ахо-Корасика. Оригинальный fgrep (grep -F) использует этот алгоритм. GNU grep
в этом случае использует Commentz-Walter алгоритм (объединение Ахо-Корасика и алгоритма
поиска строки Бойера—Мура). ripgrep (rg) иногда работает быстрее GNU grep, используя
SIMD алгоритм, называемый Teddy -- см. ripgrep is faster than {grep, ag, git grep,
ucg, pt, sift}.

Чтобы подсчитать найденные строки, можно использовать sort | uniq -c команду, предложенную
@BOPOH в комментарии к вопросу. Ещё можно использовать словарь вместо сортировки:

#!/bin/sh
grep -Fof file2 file1 |
perl -lne '$seen{$_}++ }{ while (my ($k,$v)=each %seen){print "$k $v"}'


Измерения могут показать, какая из команд (sort+uniq или perl) быстрее в данном случае.

Для сравнения можно посмотреть, сколько займёт Питон-скрипт без использования дополнительных
пакетов (например, esm), которые реализуют Ахо-Корасик-подобные алгоритмы:

#!/usr/bin/env python
import re
import sys
from collections import Counter

def main():
    # load substrings from file2
    with open('file2', 'rb') as file2:
        substrings = {line.strip() for line in file2} # unique lines
        substrings = filter(None, substrings) # filter blank lines
        substrings = sorted(substrings, key=len, reverse=True) # longest first
        pattern = b"|".join(map(re.escape, substrings))
        find_substrings = re.compile(pattern).findall

    # count substrings in file1
    counter = Counter()
    counter_update = counter.update # cache the lookup (for CPython)
    with open('file1', 'rb') as file1:
        for line in file1:
            counter_update(find_substrings(line))

    # write substrings frequencies
    write = getattr(sys.stdout, 'buffer', sys.stdout).write
    for substring, count in counter.most_common(): # most common first
        write(substring)
        write(b' ')
        write(str(count).encode())
        write(b'\n')

main()


Результат

Тест корова 2
телефон 1
Трубадур 1


Вот ещё вариант для сравнения, где строки в файле ищутся с помощью регулярного выражения
и mmap:

#!/usr/bin/env python3
import re
import sys
from collections import Counter
from mmap import ACCESS_READ, mmap
from operator import methodcaller

def generate_tokens(filename, pattern):
    with open(filename) as f, mmap(f.fileno(), 0, access=ACCESS_READ) as mm:
         yield from re.finditer(pattern, mm)

def main():
    # load substrings from file2
    with open('file2', 'rb') as file2:
        substrings = {line.strip() for line in file2} # unique lines
        substrings = filter(None, substrings) # filter blank lines
        substrings = sorted(substrings, key=len, reverse=True) # longest first
        pattern = b"|".join(map(re.escape, substrings))

    # count substrings in file1
    file1_substrings = generate_tokens('file1', pattern)
    counter = Counter(map(methodcaller('group'), file1_substrings))

    # write substrings frequencies
    write = getattr(sys.stdout, 'buffer', sys.stdout).write
    for substring, count in counter.most_common(): # most common first
        write(substring)
        write(b' ')
        write(str(count).encode())
        write(b'\n')

main()


Работает на Windows, *nix. Код для Питон 3, но его можно легко адаптировать для Питон
2, если необходимо.


Ответ 2

Решение "в лоб" (сомневаюсь, что будет быстро)))
grep -o -f file2 file1 | sort | uniq -c

5 строк в file2 и 2.7Г в file1 где-то за 4 минуты обработало.
Если не требуется для каждой отдельной строки количество считать (т.е. достаточно
общего количества), тогда можно еще проще (и немного быстрее):
grep -co -f file2 file1


Ответ 3

Ну, как вариант, можно попробовать вот так в лоб:
somelist1 = []  
somelist2 = []  
f1 = open('file1.txt')  # файл на 2mb
f2 = open('file2.txt')  # файл на 2gb

for line in f1:
    a1 = line.replace('\n', '')
    somevar = a1.split()
    for i in somevar:
        somelist1.append(i)

for line in f2:
    a2 = line.replace('\n', '')
    somevar = a2.split()
    for i in somevar:
        somelist2.append(i)

for i in somelist1:
    index = 0
    for j in somelist2:
        if i == j:
            index += 1
    print(i + " - " + str(index))

Вывод в виде:
Трубадур - 481779
Тест - 963549
корова - 1445337
телефон - 481779

Попробовал на файле в 150 мб, сделался за 5-7 секунд, время не замерял. Может, кто-то
предложит более оптимизированное решение.
UPDATE
Попробовал на файле побольше, 2gb скорее всего точно не прогрузить, этот вариант
применим только к небольшим файлам.

Поиск повторяющихся строк

Привет. Возник вопрос: Есть файл 1 ~ 2GB и есть файл 2 ~ 1MB Вопрос - как наиболее быстро подсчитать кол-во вхождений строк из файла2 в файле1? К примеру файл1: Тест корова большая Флагман большая корова Трубадур золотистый Флагманский телефон N90 Логическое оформление Тест корова Бла бла стар Файл2: Трубадур Тест корова телефон Должно получиться: Трубадур 1 Тест корова 2 телефон 1 Файл 1 много больше файл2.

Ответ

Эффективным методом поиска нескольких подстрок одновременно в большом тексте является алгоритм Ахо-Корасика. Оригинальный fgrep (grep -F) использует этот алгоритм. GNU grep в этом случае использует Commentz-Walter алгоритм (объединение Ахо-Корасика и алгоритма поиска строки Бойера—Мура). ripgrep (rg) иногда работает быстрее GNU grep, используя SIMD алгоритм, называемый Teddy -- см. ripgrep is faster than {grep, ag, git grep, ucg, pt, sift}
Чтобы подсчитать найденные строки, можно использовать sort | uniq -c команду, предложенную @BOPOH в комментарии к вопросу. Ещё можно использовать словарь вместо сортировки:
#!/bin/sh grep -Fof file2 file1 | perl -lne '$seen{$_}++ }{ while (my ($k,$v)=each %seen){print "$k $v"}'
Измерения могут показать, какая из команд (sort+uniq или perl) быстрее в данном случае.
Для сравнения можно посмотреть, сколько займёт Питон-скрипт без использования дополнительных пакетов (например, esm), которые реализуют Ахо-Корасик-подобные алгоритмы:
#!/usr/bin/env python import re import sys from collections import Counter
def main(): # load substrings from file2 with open('file2', 'rb') as file2: substrings = {line.strip() for line in file2} # unique lines substrings = filter(None, substrings) # filter blank lines substrings = sorted(substrings, key=len, reverse=True) # longest first pattern = b"|".join(map(re.escape, substrings)) find_substrings = re.compile(pattern).findall
# count substrings in file1 counter = Counter() counter_update = counter.update # cache the lookup (for CPython) with open('file1', 'rb') as file1: for line in file1: counter_update(find_substrings(line))
# write substrings frequencies write = getattr(sys.stdout, 'buffer', sys.stdout).write for substring, count in counter.most_common(): # most common first write(substring) write(b' ') write(str(count).encode()) write(b'
')
main()
Результат
Тест корова 2 телефон 1 Трубадур 1
Вот ещё вариант для сравнения, где строки в файле ищутся с помощью регулярного выражения и mmap
#!/usr/bin/env python3 import re import sys from collections import Counter from mmap import ACCESS_READ, mmap from operator import methodcaller
def generate_tokens(filename, pattern): with open(filename) as f, mmap(f.fileno(), 0, access=ACCESS_READ) as mm: yield from re.finditer(pattern, mm)
def main(): # load substrings from file2 with open('file2', 'rb') as file2: substrings = {line.strip() for line in file2} # unique lines substrings = filter(None, substrings) # filter blank lines substrings = sorted(substrings, key=len, reverse=True) # longest first pattern = b"|".join(map(re.escape, substrings))
# count substrings in file1 file1_substrings = generate_tokens('file1', pattern) counter = Counter(map(methodcaller('group'), file1_substrings))
# write substrings frequencies write = getattr(sys.stdout, 'buffer', sys.stdout).write for substring, count in counter.most_common(): # most common first write(substring) write(b' ') write(str(count).encode()) write(b'
')
main()
Работает на Windows, *nix. Код для Питон 3, но его можно легко адаптировать для Питон 2, если необходимо.