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

Question

Я ищу алгоритм, который будет принимать вектор строк v1 и возвращать аналогичный вектор строк v2, где каждая строка длиной менее x символов и является уникальной. Строки в v1 могут быть не уникальными.

Хотя мне нужно принять ASCII в v1, я бы предпочел вставлять только буквенно-цифровые символы ([A-Za-z0-9]), когда требуется вставка новых символов.

Очевидно, что здесь есть три оговорки:

1. Для некоторых значений v1 и x возможный уникальный v2 невозможен. Например, когда v1 имеет 37 элементов и x == 1.

2. «Подобный», как указано в вопросе, субъективен. Строки будут ориентированы на пользователя и предположительно короткие фразы на естественном языке (например, «количество цветов»). Я хочу, чтобы человек мог как можно проще сопоставить оригинал с укороченной строкой. Вероятно, это означает использование эвристических методов, таких как dismvoweling Поскольку, вероятно, нет никакой объективной меры моей конструкции подобия (расстояние между строками, вероятно, здесь не будет наиболее полезным, хотя это может быть), мое суждение о том, что хорошо, будет произвольным. Метод должен быть подходящим для английского - другие языки не имеют значения.

Очевидно, что это (независимая от языка программирования) проблема, но я бы положительно оценил реализацию на python (потому что я нахожу его язык обработки строк простым).

Answer 1

несколько заметок / указателей о том, как это сделать в python.

1. Используйте модуль bisect , чтобы сохранить массив результатов, чтобы легко обнаружить потенциальных неуникальных.Это полезно даже в том случае, если v1 уже отсортировано (например, name и enemy столкнется после отмены гласного)
2. Снятие гласного гласного может быть достигнуто простым вызовом .translate(None, "aeiouyAEIOUY") в строке.
3. В случае дубликатов вы можете сначала попытаться разрешить коллизии, опустив все результаты в нижний регистр и используя swapcase в качестве «битовой маски», то есть множественные вхождения aaa становятся ["aaa", "aaA", "aAa", "aAA"] и т. Д., И если этого недостаточно, «увеличивая» символы, начиная с концадо тех пор, пока не будет найден не конфликтующий идентификатор, например,["aa"]*7 станет ["aa", "aA", "Aa", "AA", "ab", "aB", "Ab"]

Answer 2

Sketch -

Разработка списка функций, уменьшающих размер английской строки.Упорядочить функции от наименее до самых непонятных.

Для каждой строки в v1 неоднократно применяйте функцию затемнения, пока она больше не сможет уменьшить размер строки, а затем переходите к следующей функции.

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

Ниже приведены некоторые идеи для функций уменьшения размера, субъективно упорядоченных от наименьшего к наиболее скрывающему.(Случайный выбор предназначен для увеличения вероятности того, что уменьшенная строка будет уникальной.)

1. Заменить случайное вхождение символов двух пробелов на один пробел
2. Заменить случайное вхождениепунктуации с последующим пробелом с одним пробелом
3. Удалить случайное слово из одного символа, которое также является членом списка уничтожений (например, "I", "a")
4. Удалить двапроизвольное символьное слово, которое также является членом списка уничтожений (например, «an», «of»)
5. Удаление произвольного трехсимвольного слова, которое также является членом списка уничтожений (например, «the»), "и")
6. Заменить слово из пяти или более слов словом, состоящим из первых трех и последнего символа (например, «число» становится «numr», «цвета» становится «colrs»)
7. Удалить гласный в случайном порядке
8. Удалить слово, которое встречается в большом количестве строк в v1.Идея состоит в том, что очень распространенные слова имеют низкое значение.
9. Переведите слово / фразу в более короткое слово "номерной знак" на основе словаря (тезауруса) (например, http://www.baac.net/michael/plates/index.html) * 1034.*

(Примечание: для двух последних функций потребуется доступ к исходной неизмененной строке и соответствия между неизмененными и измененными словами.)

Answer 3

def split_len(seq, length):
    return [seq[i:i+length] for i in range(0, len(seq), length)]
newListOfString=[]
for item in listOfStrings:
    newListOfString.append(split_len(item,8)[0])

возвращает первые восемь символов.