нахождение долго повторяемых подстрок в крупной строке
Swift 4:
var totalTime = 10
var countdownTimer: Timer!
@IBOutlet weak var timeLabel: UILabel!
override func viewDidLoad() {
super.viewDidLoad()
startTimer()
}
Этот вызов метода инициализирует таймер. Он определяет timeInterval (как часто будет вызываться метод) и селектор (вызываемый метод).
Интервал измеряется секундами, поэтому, чтобы он работал как стандартные часы, мы должны установить этот аргумент в 1.
func startTimer() {
countdownTimer = Timer.scheduledTimer(timeInterval: 1, target: self, selector: #selector(updateTime), userInfo: nil, repeats: true)
}
// Stops the timer from ever firing again and requests its removal from its run loop.
func endTimer() {
countdownTimer.invalidate()
}
//updateTimer is the name of the method that will be called at each second. This method will update the label
@objc func updateTime() {
timeLabel.text = "\(totalTime)"
if totalTime != 0 {
totalTime -= 1
} else {
endTimer()
}
}
8 ответов
The effective way to do this is to create an index of the sub-strings, and sort them. This is an O(n lg n) operation.
BWT compression does this step, so its a well understood problem and there are radix and suffix (claim O(n)) sort implementations and such to make it as efficient as possible. It still takes a long time, perhaps several seconds for large texts.
If you want to use utility code, C++ std::stable_sort() performs much better than std::sort() for natural language (and much faster than C's qsort(), but for different reasons).
Then visiting each item to see the length of its common substring with its neighbours is O(n).
Вы могли посмотреть на находящиеся на диске суффиксные деревья. Я нашел эту библиотеку реализации Суффиксного дерева через Google плюс набор статей, которые могли помочь реализации его самостоятельно.
Вы могли решить это использование, делят и завоевывают. Я думаю, что это должно быть той же алгоритмической сложностью как использование trie, но возможно менее мудрый эффективным внедрением
void LongSubstrings(string data, string prefix, IEnumerable<int> positions)
{
Dictionary<char, DiskBackedBuffer> buffers = new Dictionary<char, DiskBackedBuffer>();
foreach (int position in positions)
{
char nextChar = data[position];
buffers[nextChar].Add(position+1);
}
foreach (char c in buffers.Keys)
{
if (buffers[c].Count > 1)
LongSubstrings(data, prefix + c, buffers[c]);
else if (buffers[c].Count == 1)
Console.WriteLine("Unique sequence: {0}", prefix + c);
}
}
void LongSubstrings(string data)
{
LongSubstrings(data, "", Enumerable.Range(0, data.Length));
}
После этого необходимо было бы сделать класс, который реализовал DiskBackedBuffer, таким образом, что это был список чисел, и когда буфер добрался до определенного размера, он испишется к диску с помощью временного файла и вспомнит из диска, когда считано из.
Ответ на мой собственный вопрос:
Учитывая, что долгое соответствие является также коротким соответствием, можно обменять несколько передач на RAM первыми находящими более короткими соответствиями и затем видящий, можно ли 'вырастить' эти соответствия.
Литеральный подход к этому должен создать trie (с количествами в каждом узле) всех последовательностей некоторой фиксированной длины в данных. Вы затем отбираете все те узлы, которые не соответствуют Вашим критериям (например, самое долгое соответствие). Затем затем сделайте последующую передачу через данные, пристроив trie глубже, но не более широкие. Повторитесь, пока Вы не нашли самую длинную повторную последовательность (последовательности).
Хороший друг предложил использовать хеширование. Путем хеширования последовательности символов фиксированной длины, запускающейся в каждом символе, у Вас теперь есть проблема нахождения дублирующихся значений хэш-функции (и проверка дублирования, поскольку хеширование с потерями). При выделении массива длина данных для содержания значений хэш-функции, можно сделать интересные вещи, например, видеть, дольше ли соответствие, чем передача фиксированной длины данных, можно просто сравнить последовательности хешей вместо того, чтобы повторно создать их. И т.д.
Можно ли решить проблему путем создания суффиксного массива вместо этого? Иначе необходимо будет, вероятно, использовать одно из находящихся на диске суффиксных деревьев, упомянутых в других ответах.
Этот текст с разрывами слова? Затем я подозревал бы, что Вы хотите изменение ключевого слова в контексте: сделайте копию каждой строки n временами для n слов в строке, повредив каждую строку в каждом слове; альфа вида всего этого; ищите повторения.
Если это - единственная длинная гудящая строка, как говорят, что биоинформатические последовательности DNA, то Вы хотите создать что-то как свой trie на диске; создайте запись для каждого символа с дисковым смещением для следующих узлов. Я взглянул бы на Объем 3 из Knuth, разделил бы 5.4, "внешняя сортировка".
Просто запоздалая мысль, которая произошла со мной...
В зависимости от Вашей ОС/среды. (Например, указатели на 64 бита и mmap () доступный.)
Вы смогли создавать очень большое Суффиксное дерево на диске через mmap () и затем сохранять кэшируемое most-frequently-accessed подмножество того дерева в памяти.
Самый легкий путь мог бы просто состоять в том, чтобы швырнуть 100$ для набора больше RAM. Иначе необходимо будет, вероятно, посмотреть на поддержанные структуры диска для содержания суффиксного дерева.