localizar texto-duplicado
https://stackoverflow.com/questions/859739
-
21-08-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
O meu principal problema é tentar encontrar uma solução adequada para transformar automaticamente esta, por exemplo:
d+c+d+f+d+c+d+f+d+c+d+f+d+c+d+f+
a este:
[d+c+d+f+]4
i. duplicatas encontrar ao lado do outro, em seguida, fazendo um "loop" mais curto fora destas duplicatas. Até agora eu não encontrei nenhuma solução adequada para isso, e eu olho para a frente a uma resposta. P. S. Para confusão evitar, a amostra acima mencionada não é a única coisa que precisa "looping", ele difere do arquivo para arquivo. Oh, e isso é destinado a um programa C # C ++ ou, tampouco é bom, embora eu estou aberto a outras sugestões também. Além disso, a idéia principal é que todo o trabalho seria feito pelo próprio programa, nenhuma entrada do usuário, exceto para o próprio arquivo. Aqui está o arquivo completo, para referência, as minhas desculpas para a página esticada: # 0 @ 16 V225 Y10 W250 T76
l16
$ ED $ EF $ A9
p20,20
> Ecegb> d
/
l8
r1r1r1r1
f + f + g + cg + r4
a + c + a + g + cg + R4f + f + g + cg + r4
a + c + a + g + cg + R4f + f + g + cg + r4
a + c + a + g + CG + r4
f + f + g + cg + r4
a + c + a + g + + R4G 16f16c +
a + 2 ^ g + f + g + 4
f + ff + 4FD + f4
d + c + d + 4c + c C4d +
# 4 @ 22 V250 Y10
l8 o3 rg rg + + + rg rg rg + + + rg rg rg + + + rg rg rg + + + rg rg rg + + + rg rg rg + + + rg rg rg + + + rg rg rg + + + rg / r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1
# 2 @ 4 V155 Y10
l8 $ ED $ F8 $ 8F o4 r1r1r1 d + 4f4f + 4G + 4 a + 4R1 ^ 4 ^ 2 / D + 4 ^ FR2 F + 4 + 4 ^ fr2d ^ FR2 F + 4 + 4 ^ fr2d ^ FR2 F + 4 + 4 ^ fr2d ^ FR2 F + 4 ^ FR2 > D + 4 ^ FR2 F + 4 + 4 ^ fr2d ^ FR2 F + 4 ^ FR2 < f + 4 ^ g + r2 f + 4 + 4 ^ fr2f ^ g + r2 f + 4 + 4 ^ fr2f ^ g + r2 f + 4 + 4 ^ fr2f ^ g + r2 f + 4 + 4 ^ fr2f ^ g + r2 f + 4 + 4 ^ fr2f ^ g + r2 f + 4 + 4 ^ fr2f ^ g + r2 f + 4 + 4 ^ fr2f ^ g + r2 F + 4 ^ FR2 > a + 4 ^ g + r2 f + 1A + 4 ^ g + r2 f + 1 F + 4 ^ FR2 d + 1 F + 4 ^ FR2 d + 2 ^ d + 4 ^ r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1
# 3 @ 10 v210 Y10
r1 ^ 1
o3
c8r8d8r8
c8r8c8r8c8r8c8r8c8r8c8r8c8r8c8r8c8r8c8r8c8r8
c8
@ 10d16d16 @ 21
c8
@ 10d16d16 @ 21
c8
@ 10d16d16 @ 21
/
c4 @ 10d8 @ 21c8 # 7 @ 16 V230 Y10 l16
$ ED $ EF $ A9
cceeggbbggeeccee
# 5 @ 4 v155 Y10 l8
$ ED $ F8 $ 8F
o4
r1r1r1r1
d + 4R1 ^ 2 ^ 4
/
cr2
c + 4 ^ CR2 cr2
c + 4 ^ CR2 cr2
c + 4 ^ CR2 cr2
c + 4 ^ CR2
a + 4 ^> cr2
c + 4 ^ CR2
cr2
c + 4 ^ c
r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1r1
r2
F + 4 ^ FR2
d + 1F + 4 ^ FR2
d + 1
c + 4 ^ CR2
C + 4 ^ CR2
Solução
Não sei se isso é o que você está procurando.
Eu levei a string "testtesttesttest4notaduped + c + d + f + d + c + d + f + d + c + d + f + d + c + d + f + testtesttest" e converteu-a "[teste] 4 4notadupe [d + c + d + f +] 4 [teste] 3 "
Eu tenho certeza que alguém vai chegar a uma melhor solução mais eficiente, uma vez que é um pouco lento ao processar seu arquivo completo. Estou ansioso para outras respostas.
string stringValue = "testtesttesttest4notaduped+c+d+f+d+c+d+f+d+c+d+f+d+c+d+f+testtesttest";
for(int i = 0; i < stringValue.Length; i++)
{
for (int k = 1; (k*2) + i <= stringValue.Length; k++)
{
int count = 1;
string compare1 = stringValue.Substring(i,k);
string compare2 = stringValue.Substring(i + k, k);
//Count if and how many duplicates
while (compare1 == compare2)
{
count++;
k += compare1.Length;
if (i + k + compare1.Length > stringValue.Length)
break;
compare2 = stringValue.Substring(i + k, compare1.Length);
}
if (count > 1)
{
//New code. Added a space to the end to avoid [test]4
//turning using an invalid number ie: [test]44.
string addString = "[" + compare1 + "]" + count + " ";
//Only add code if we are saving space
if (addString.Length < compare1.Length * count)
{
stringValue = stringValue.Remove(i, count * compare1.Length);
stringValue = stringValue.Insert(i, addString);
i = i + addString.Length - 1;
}
break;
}
}
}
Outras dicas
Você pode usar o algoritmo de Smith-Waterman para fazer o alinhamento local, comparando a string contra si mesmo.
http://en.wikipedia.org/wiki/Smith-Waterman_algorithm
EDIT: Para adaptar o algoritmo de auto alinhamento, você precisa para valores de força na diagonal a zero - isto é, penalizar a solução trivial de alinhar a seqüência inteira exatamente com ele mesmo. Em seguida, o "segundo melhor" alinhamento irá aparecer em seu lugar. Este será os dois maiores substrings correspondentes. Repita o mesmo tipo de coisa para encontrar substrings correspondentes progressivamente mais curtos.
LZW pode ajudar: ele usa prefixos dicionário para procurar padrões repetitivos e substitui esses dados com referências a entradas anteriores. Eu acho que não deve ser difícil para adaptá-lo às suas necessidades.
Por que não usar System.IO.Compression ?
