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

Question

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

a22tbf645
92STbfF4W
92rtRe7Ev
gyue73Pr4
u8t9D03gE
a2t4TA6Kk
Lj3D2Jrs1

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

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

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

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

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

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

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

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

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

Answer 1

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

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)

Answer 2

Решение с использованием простой машины состояний (детерминированного конечного автомата) было написано "в лоб" на 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)

Answer 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?