Алгоритм разбиения строки (предложения,текста) на несколько строк, с заданными длинами результирующих строк

17.03.16

Разработка - Математика и алгоритмы

Представляю вашему вниманию очередной алгоритм разбиения строки на подстроки, с возможностью определения длин результирующих строк.

Скачать исходный код

Наименование Файл Версия Размер
ОтладкаРазбиенияСтроки.epf
.epf 9,96Kb
2
.epf 9,96Kb 2 Скачать

Возник вопрос написания такого алгоритма переноса строки. Задача была следующая - необходимо разбивать строку текста под заданные графы в печатной форме и размещать эту строку там. В качестве признаков допустимости переноса были выбраны символы пробела, запятой, точки с запятой (при необходимости - можно модифицировать саму функцию переноса). Прилагается обработка для теста самого алгоритма, в которой необходимо внести исходную строку и задать размеры строк разбиения.

Текст самой процедуры:

//Функция разбивает строку на подстроки, по заданным размерам строк
//Параметры:СтрокаРазбиения - исходная строка любого размера
//МассивРазмераСтрок - Массив с данными о размерах строк
//Возврат - обработанная строка
Функция РазбитьТекстПоМассивуРазмераСтрок(СтрокаРазбиения, МассивРазмераСтрок)
	
	МассивВозврата = Новый Массив;
	
	МассивРазделителей = новый Массив;
	МассивРазделителей.Добавить(" ");
	МассивРазделителей.Добавить(",");
	МассивРазделителей.Добавить(";");

	СтрокаВозврата = "";
	ИндексМассиваРазмераСтрок = 0;
	Слово = "";
	
	Для Сч = 1 По СтрДлина(СтрокаРазбиения) Цикл
		
		Символ = Сред(СтрокаРазбиения,Сч,1);
		
		Если МассивРазделителей.Найти(Символ) = Неопределено И Сч <> СтрДлина(СтрокаРазбиения) Тогда //
			Слово = Слово + Символ;
		Иначе
			
			Если СтрДлина(СтрокаВозврата) + СтрДлина(Слово) <= МассивРазмераСтрок[ИндексМассиваРазмераСтрок] Тогда    //Если Вмещаемся
				
				Слово = Слово + Символ;
				
				СтрокаВозврата = СтрокаВозврата+Слово;
				Слово = "";
				
			ИначеЕсли ИндексМассиваРазмераСтрок = МассивРазмераСтрок.Количество()-1 Тогда      //Если это последняя строка
				
				Если МассивВозврата.Количество() = МассивРазмераСтрок.Количество() Тогда
					Прервать;
				КонецЕсли;

				СтрокаВозврата = СтрокаВозврата+Слово;
				МассивВозврата.Добавить(Лев(СтрокаВозврата,МассивРазмераСтрок[ИндексМассиваРазмераСтрок]));
				СтрокаВозврата = "";
				Слово ="";
				Прервать;
				
			Иначе//Если не вмещаемся
				
				Если СтрДлина(Слово) > МассивРазмераСтрок[ИндексМассиваРазмераСтрок] И СтрокаВозврата="" Тогда //Если слово больше чем доступная длинна строки
					
					Если МассивВозврата.Количество() = МассивРазмераСтрок.Количество() Тогда
						Прервать;
					КонецЕсли;

					МассивВозврата.Добавить(Лев(Слово,МассивРазмераСтрок[ИндексМассиваРазмераСтрок]));
					

					Слово = Сред(Слово,МассивРазмераСтрок[ИндексМассиваРазмераСтрок]+1);  
					Слово = Слово + Символ;
					ИндексМассиваРазмераСтрок = ИндексМассиваРазмераСтрок+ 1;

							
				Иначе
					Если МассивВозврата.Количество() = МассивРазмераСтрок.Количество() Тогда
						Прервать;
					КонецЕсли;
					
					МассивВозврата.Добавить(СокрЛП(СтрокаВозврата));
					СтрокаВозврата = "";
					ИндексМассиваРазмераСтрок = ИндексМассиваРазмераСтрок+ 1;
					Сч = Сч - 1;
					Продолжить;
					
				КонецЕсли;
			КонецЕсли;
			
		КонецЕсли;
		
	КонецЦикла;
	
	Если ЗначениеЗаполнено(СтрокаВозврата+Слово) И МассивВозврата.Количество() < МассивРазмераСтрок.Количество() Тогда
	
		МассивВозврата.Добавить(Лев(СтрокаВозврата+Слово,МассивРазмераСтрок[ИндексМассиваРазмераСтрок]));
		
	КонецЕсли;
	
	Возврат(МассивВозврата);
	
КонецФункции

Разбиение строки разбиение перенос

См. также

Метод Дугласа-Пойкера для эффективного хранения метрик

Математика и алгоритмы Платформа 1C v8.2 Конфигурации 1cv8 Россия Абонемент ($m)

На написание данной работы меня вдохновила работа @glassman «Переход на ClickHouse для анализа метрик». Автор анализирует большой объем данных, много миллионов строк, и убедительно доказывает, что ClickHouse справляется лучше PostgreSQL. Я же покажу как можно сократить объем данных в 49.9 раз при этом: 1. Сохранить значения локальных экстремумов 2. Отклонения от реальных значений имеют наперед заданную допустимую погрешность.

1 стартмани

30.01.2024    1870    stopa85    12    

34

Алгоритм симплекс-метода для решения задачи раскроя

Математика и алгоритмы Бесплатно (free)

Разработка алгоритма, построенного на модели симплекс-метода, для нахождения оптимального раскроя.

19.10.2023    4666    user1959478    50    

34

Регулярные выражения на 1С

Математика и алгоритмы Инструментарий разработчика Платформа 1С v8.3 Мобильная платформа Россия Абонемент ($m)

Что ж... лучше поздно, чем никогда. Подсистема 1С для работы с регулярными выражениями: разбор выражения, проверка на соответствие шаблону, поиск вхождений в тексте.

1 стартмани

09.06.2023    7656    4    SpaceOfMyHead    17    

56

Модель распределения суммы по базе

Математика и алгоритмы Платформа 1С v8.3 Россия Абонемент ($m)

Обычно под распределением понимают определение сумм пропорционально коэффициентам. Предлагаю включить сюда также распределение по порядку (FIFO, LIFO) и повысить уровень размерности до 2-х. 1-ое означает, что распределение может быть не только пропорциональным, но и по порядку, а 2-ое - это вариант реализации матричного распределения: по строкам и столбцам. Возможно вас заинтересует также необычное решение этой задачи через создание DSL на базе реализации текучего интерфейса

1 стартмани

21.03.2022    7932    7    kalyaka    11    

44

Изменения формата файлов конфигурации (CF) в 8.3.16

Математика и алгоритмы Платформа 1С v8.3 Бесплатно (free)

Дополнение по формату файлов конфигурации (*.cf) в версии 8.3.16.

16.12.2021    4546    fishca    13    

36

Интересная задача на Yandex cup 2021

Математика и алгоритмы Бесплатно (free)

Мое решение задачи на Yandex cup 2021 (frontend). Лабиринт. JavaScript.

12.10.2021    8937    John_d    73    

46

Механизм анализа данных. Кластеризация.

Математика и алгоритмы Анализ учета Платформа 1С v8.3 Анализ и прогнозирование Бесплатно (free)

Подробный разбор, с примером использования, встроенного механизма кластеризации 1С.

31.08.2021    7959    dusha0020    8    

70
Комментарии
Подписаться на ответы Сортировка: Древо развёрнутое
Свернуть все
1. Гость 17.03.16 16:45
2. Alias 176 17.03.16 17:36 Сейчас в теме
Ну как сказать... оно конечно работает, несмотря на некоторые огрехи. Например, если разделитель попадёт как раз в конец блока, то строка будет на один символ длиннее разрешённой (см. пример ниже). Ну и наверняка будут неточности в сложных случаях -- типа длинной строки из пробелов или сплошных разделителей и т.д. Считаем, что сложные случаи мы не рассматриваем.

А вот если оценить сложность(размер кода) алгоритма и его оптимальность, то тут ещё есть куда расти.

Например, самая трудозатратная операция (МассивРазделителей.Найти(Символ) = Неопределено) выполняется столько раз, сколько букв в исходной строке. В сумме это составляет около 30% всего времени выполнения алгоритма! Это очень много, зачем? В моём примере реализации той же задачи (опять же, см. ниже) этот оператор вызывается на порядок меньше раз (32 против 486). Из-за этого общее время выполнения снижено с 0.003427 до 0.000324 (опять же, меньше на порядок).

По количеству кода мой вариант набросанный на коленке уместился в 27 строк, у автора -- 43. Зачем столько писать для реализации такой простой задачи?

Мой вариант (простите, не знаю как раскрасить):

	Для ИндексМассиваРазмераСтрок=0 по МассивРазмераСтрок.ВГраница() Цикл
		СчСимв = МассивРазмераСтрок[ИндексМассиваРазмераСтрок];
		
		СтрокаРазбиения = СокрЛ(СтрокаРазбиения); // убрать левые пробелы (остальные разделители пусть уж остаются)
		
		ПримерныйОтвет = Лев(СтрокаРазбиения, СчСимв);
		Если СтрДлина(СтрокаРазбиения)>СчСимв Тогда // есть разбиение, т.к. строка продолжается
			ДляКрасотыУбратьРазделительПоКоторомуРазделили = 0; // (если разделение пройдёт точно по разделителю)
			Если МассивРазделителей.Найти(Сред(СтрокаРазбиения, СчСимв+1, 1))=Неопределено  Тогда // и разбили неудачно, не по концу слова
				Пока СчСимв>0 И МассивРазделителей.Найти(Сред(ПримерныйОтвет, СчСимв, 1))=Неопределено Цикл // от конца блока взад ищем ближайший разделитель
					СчСимв=СчСимв-1;
				КонецЦикла;
			Иначе // повезло, разделили как раз по разделителю...
				ДляКрасотыУбратьРазделительПоКоторомуРазделили = 1;
			КонецЕсли;
		Иначе // строка закончилась уже, и так сойдёт
			СчСимв = 0;
		КонецЕсли;
		
		Если СчСимв=0 Тогда // не нашли разделителя или он был и не нужен
			МассивВозврата.Добавить(СокрП(ПримерныйОтвет));
		Иначе // нашли разделитель
			ПримерныйОтвет = Лев(ПримерныйОтвет,СчСимв);
			МассивВозврата.Добавить(СокрП(ПримерныйОтвет));
		КонецЕсли;
		
		СтрокаРазбиения = Сред(СтрокаРазбиения, СтрДлина(ПримерныйОтвет)+1+ДляКрасотыУбратьРазделительПоКоторомуРазделили);
		
		Если СтрДлина(СтрокаРазбиения)=0 Тогда
			Прервать;
		КонецЕсли;
	КонецЦикла;
Показать

Огрехи авторского алгоритма, и результат моего:
70[;Возник вопрос написания такого алгоритма переноса строки. Задача] (длина 66)
60[была следующая - необходимо разбивать строку текста под] (длина 55)
50[заданные графы в печатной форме и размещать эту;] (длина 51) разрешено всего 50
40[строку там. В качестве признаков] (длина 32)
50[допустимости переноса были выбраны символы пробела,] (длина 51) разрешено всего 50
60[запятой, точки с запятой (при необходимости - можно] (длина 51)
70[модифицировать саму функцию переноса). Прилагается обработка для теста] (длина 70)
60[самого алгоритма, в которой необходимо внести исходную] (длина 54)
50[строку и задать размеры строк разбиения.] (длина 40)
------------------
70[;Возник вопрос написания такого алгоритма переноса строки. Задача] (длина 66)
60[была следующая - необходимо разбивать строку текста под] (длина 55)
50[заданные графы в печатной форме и размещать эту] (длина 50)
40[строку там. В качестве признаков] (длина 32)
50[допустимости переноса были выбраны символы пробела] (длина 50)
60[запятой, точки с запятой (при необходимости - можно] (длина 51)
70[модифицировать саму функцию переноса). Прилагается обработка для теста] (длина 70)
60[самого алгоритма, в которой необходимо внести исходную] (длина 54)
50[строку и задать размеры строк разбиения.] (длина 40)
3. starik-2005 3036 19.03.16 13:06 Сейчас в теме
Как-то слишком много текста в функции. Сдается мне, что можно все в 10 строк уложить...
4. SiAl 76 14.04.16 11:43 Сейчас в теме
Молодец. Но я бы лично использовал регулярные выражения, в WIndows, например, - RegExp. Правда решение не универсально, но объем кода меньше, и работать будет шустрее
5. fixin 4253 22.09.22 09:09 Сейчас в теме
Спасибо, но не хватает разбивки по заданной ширине строки.
Я искал, чтобы заголовок колонки таблицы перенести на несколько строк.
Оставьте свое сообщение