Re: Squeezing spaces out of a string

joe.celko_at_northface.edu (--CELKO--) wrote in message news:<a264e7ea.0401311609.7c93100a_at_posting.google.com>...
> This problem comes up on newsgroup about once a year. Given a
> VARCHAR(n) column with words in it, how do you squeeze out the extra
> spaces, that each word is separated by only one space?
>
> You can nest function calls up to 32 levels deep in SQL Server and
> they have REPLACE (<target string>, <old string>, <new string>)
> function, so answer is simply:
>
> UPDATE Foobar
> SET col_x
> = REPLACE (
> REPLACE (
> REPLACE (
> ..
> REPLACE(col_x, ' ', ' ')
> ..
> ' ', ' ')
> ' ', ' ')
> ' ', ' ');
>
> This is a LOT faster than hanging in a loop and it is pure SQL, not
> proprietary, procedural code. But now a matb problem for you: let
> col_x be VARCHAR(n). What is the optimal mix of replace function
> calls and what should they look like for the general case of (n)?
> There can be more than one word in the string, so you can have what
> typeseters call "rivers" in the string.
>
> Prove it.
>
> Let (j->k) mean "replaces (j) spaces with (k) spaces"
>
> a) (2->1) repeated log2(n) times?
> b) Is it best to always have (k->1)?
> c) (floor(sqrt(n)) -> 1) as a starter?
> d) Fibonnaci series?
>
> I am in a weird mood this afternoon, so I'll offer a book as a prize
> for a proof.

>

Sorry, no proof. Just some reflections. If we think of the string as a sequence of spacecontainers:

S = {s_1, s_2, ..., s_n}

Since I dont think there is one optimal sequense of replacement operators for all strings, we will have to investigate the length of all s_i to find the optimal sequence. But this problem is somewhat similar to the original one. Therefore, I would go for alternative a)

Kind regards
/Lennart Received on Wed Feb 04 2004 - 10:56:06 CET