source: trunk/CrypPlugins/CostFunction/CostFunction.cs @ 1376

Last change on this file since 1376 was 1376, checked in by malischewski, 12 years ago

Working on it..

File size: 26.4 KB
Line 
1/*                             
2   Copyright 2009 Team CrypTool (Sven Rech,Dennis Nolte,Raoul Falk,Nils Kopal), Uni Duisburg-Essen
3
4   Licensed under the Apache License, Version 2.0 (the "License");
5   you may not use this file except in compliance with the License.
6   You may obtain a copy of the License at
7
8       http://www.apache.org/licenses/LICENSE-2.0
9
10   Unless required by applicable law or agreed to in writing, software
11   distributed under the License is distributed on an "AS IS" BASIS,
12   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13   See the License for the specific language governing permissions and
14   limitations under the License.
15*/
16
17using System;
18using System.Collections.Generic;
19using System.Collections;
20using System.Linq;
21using System.Text;
22using Cryptool.PluginBase.Cryptography;
23using Cryptool.PluginBase;
24using Cryptool.PluginBase.Miscellaneous;
25using Cryptool.PluginBase.Analysis;
26using System.ComponentModel;
27using Cryptool.PluginBase.Control;
28using System.IO;
29using System.Text.RegularExpressions;
30using System.Threading;
31namespace Cryptool.Plugins.CostFunction
32{
33    [Author("Nils Kopal", "Nils.Kopal@cryptool.org", "Uni Duisburg-Essen", "http://www.uni-due.de")]
34    [PluginInfo(false, "CostFunction", "CostFunction", null, "CostFunction/icon.png")]
35    public class CostFunction : IAnalysisMisc
36    {
37        #region private variables
38        private CostFunctionSettings settings = new CostFunctionSettings();
39        private byte[] inputText = null;
40        private byte[] outputText = null;
41        private double value = 0;
42        private Boolean stopped = true;
43        private IControlCost controlSlave;
44        private String bigramInput;
45        private double[,] bigramMatrix;
46        private IDictionary<string, double[]> corpusGrams;
47
48        private IDictionary<string, double[]> corpusBigrams; // Used for Weighted Bigrams/Trigrams Cost function
49        private IDictionary<string, double[]> corpusTrigrams;
50
51        private DataManager dataMgr = new DataManager();
52        private const string DATATYPE = "transposition";
53
54        private IDictionary<String, DataFileMetaInfo> txtList;
55        private IDictionary<int, IDictionary<string, double[]>> statistics;
56
57        #endregion
58        #region internal constants
59        internal const int ABSOLUTE = 0;
60        internal const int PERCENTAGED = 1;
61        internal const int LOG2 = 2;
62        internal const int SINKOV = 3;
63        #endregion
64        #region CostFunctionInOut
65
66        [PropertyInfo(Direction.InputData, "Text Input", "Input your Text here", "", DisplayLevel.Beginner)]
67        public byte[] InputText
68        {
69            get
70            {
71                return inputText;
72            }
73            set
74            {
75                this.inputText = value;
76                OnPropertyChanged("InputText");
77            }
78        }
79
80        [PropertyInfo(Direction.OutputData, "Text Output", "Your Text will be send here", "", DisplayLevel.Beginner)]
81        public byte[] OutputText
82        {
83            get
84            {
85                return outputText;
86            }
87            set
88            {
89                this.outputText = value;
90                OnPropertyChanged("OutputText");
91            }
92        }
93
94        [PropertyInfo(Direction.OutputData, "Value", "The value of the function will be send here", "", DisplayLevel.Beginner)]
95        public double Value
96        {
97            get
98            {
99                return value;
100            }
101            set
102            {
103                this.value = value;
104                OnPropertyChanged("Value");
105            }
106        }
107
108        [PropertyInfo(Direction.ControlSlave, "SDES Slave", "Direct access to SDES.", "", DisplayLevel.Beginner)]
109        public IControlCost ControlSlave
110        {
111            get
112            {
113                if (controlSlave == null)
114                    controlSlave = new CostFunctionControl(this);
115                return controlSlave;
116            }
117        }
118
119        #endregion
120
121        #region IPlugin Members
122
123        public event GuiLogNotificationEventHandler OnGuiLogNotificationOccured;
124        public event PluginProgressChangedEventHandler OnPluginProgressChanged;
125
126
127        public ISettings Settings
128        {
129            get { return this.settings; }
130            set { this.settings = (CostFunctionSettings)value; }
131        }
132
133        public System.Windows.Controls.UserControl Presentation
134        {
135            get { return null; }
136        }
137
138        public System.Windows.Controls.UserControl QuickWatchPresentation
139        {
140            get { return null; }
141        }
142
143        public void PreExecution()
144        {
145            this.stopped = false;
146        }
147
148        public void Execute()
149        {
150            if (this.InputText is Object && this.stopped == false)
151            {
152                int bytesToUse = 0;
153                try
154                {
155                    bytesToUse = int.Parse(settings.BytesToUse);
156                }
157                catch (Exception ex)
158                {
159                    GuiLogMessage("Entered bytesToUse is not an integer: " + ex.Message, NotificationLevel.Error);
160                    return;
161                }
162
163                if (bytesToUse > this.InputText.Length)
164                {
165                    bytesToUse = 0;
166                }
167
168                byte[] array;
169
170                if (bytesToUse > 0)
171                {
172                    //Create a new Array of size of bytesToUse if needed
173                    array = new byte[bytesToUse];
174                    for (int i = 0; i < bytesToUse && i < this.InputText.Length; i++)
175                    {
176                        array[i] = InputText[i];
177                    }
178                }
179                else
180                {
181                    array = this.InputText;
182                }
183
184                ProgressChanged(0.5, 1);
185                bigramInput = ByteArrayToString(array);
186                switch (settings.FunctionType)
187                {
188
189                    case 0: // Index of Coincedence
190                        this.Value = calculateIndexOfCoincidence(array);
191                        break;
192
193                    case 1: // Entropy
194                        this.Value = calculateEntropy(array);
195                        break;
196
197                    case 2: // Log 2 Bigrams
198                        this.Value = calculateNGrams(bigramInput, 2, 2);
199                        break;
200
201                    case 3: // sinkov Bigrams
202                        this.Value = calculateNGrams(bigramInput, 2, 3);
203                        break;
204                    case 4: //percentaged Bigrams
205                        this.Value = calculateNGrams(bigramInput, 2, 1);
206                        break;
207                    case 5: //regular expressions
208                        this.Value = regex(bigramInput);
209                        break;
210                    case 6: // Weighted Bigrams/Trigrams (used by genetic algorithm in transposition analyser
211                        this.Value = calculateWeighted(bigramInput);
212                        break;
213
214                    default:
215                        this.Value = -1;
216                        break;
217                }//end switch               
218
219                this.OutputText = this.InputText;
220                ProgressChanged(1, 1);
221
222            }//end if
223
224        }
225
226
227
228        public void PostExecution()
229        {
230            this.stopped = true;
231        }
232
233        public void Pause()
234        {
235
236        }
237
238        public void Stop()
239        {
240            this.stopped = false;
241        }
242
243        public void Initialize()
244        {
245
246        }
247
248        public void Dispose()
249        {
250
251        }
252
253        #endregion
254
255        #region INotifyPropertyChanged Members
256
257        public event System.ComponentModel.PropertyChangedEventHandler PropertyChanged;
258
259        public void OnPropertyChanged(string name)
260        {
261            EventsHelper.PropertyChanged(PropertyChanged, this, new PropertyChangedEventArgs(name));
262        }
263
264        private void ProgressChanged(double value, double max)
265        {
266            EventsHelper.ProgressChanged(OnPluginProgressChanged, this, new PluginProgressEventArgs(value, max));
267        }
268
269        public void GuiLogMessage(string p, NotificationLevel notificationLevel)
270        {
271            EventsHelper.GuiLogMessage(OnGuiLogNotificationOccured, this, new GuiLogEventArgs(p, this, notificationLevel));
272        }
273
274        #endregion
275
276        #region IPlugin Members
277
278        public event StatusChangedEventHandler OnPluginStatusChanged;
279
280        #endregion
281
282        #region private methods
283
284
285        //public double contains(string input)
286        //{
287        //    if (settings.Contains == null)
288        //    {
289        //        GuiLogMessage("There is no text to be searched for. Please insert text in the 'Contains text / Regular Expression' - Textarea", NotificationLevel.Error);
290        //        return new Double();
291        //    }
292
293        //    if (input.Contains(settings.Contains))
294        //    {
295        //        return 1.0;
296        //    }
297        //    return -1.0;
298        //}
299        public double calculateWeighted(string input)
300        {
301
302
303            this.statistics = new Dictionary<int, IDictionary<string, double[]>>();
304           
305            if (corpusBigrams == null)
306            {
307                if (corpusTrigrams == null)
308                {
309
310                    corpusBigrams = GetStatistics(2); // Get Known Language statistics for Bigrams
311                    corpusTrigrams = GetStatistics(3); // and Trigrams
312                }
313
314            }
315            input = input.ToUpper();
316
317            /* debug foreach (KeyValuePair<string,double[]> g in corpusTrigrams)
318             {
319                 GuiLogMessage(corpusTrigrams[g.Key][0].ToString()+ " "+g.Key, NotificationLevel.Debug);
320             } */
321
322
323            Dictionary<string, double> inputBiGrams = new Dictionary<string,double>();
324            Dictionary<string, double> inputTriGrams = new Dictionary<string,double>();
325
326            // Count input Bigrams
327            foreach (string g in GramTokenizer.tokenize(input, 2, false))
328            {
329                if (inputBiGrams.ContainsKey(g))
330                {
331                    inputBiGrams[g] = inputBiGrams[g] + 1;
332                }
333                else
334                {
335                    inputBiGrams.Add(g, 0);
336                }
337            }
338            /*debug
339            foreach (KeyValuePair<string, double[]> g in corpusBigrams)
340            {
341                GuiLogMessage(corpusBigrams[g.Key][0].ToString() + " " + g.Key + " " + corpusBigrams[g.Key][1].ToString(), NotificationLevel.Debug);
342            } */
343           
344            // Count input TriGrams
345            foreach (string g in GramTokenizer.tokenize(input, 3, false))
346            {
347                if (inputTriGrams.ContainsKey(g))
348                {
349                    inputTriGrams[g] = inputTriGrams[g] + 1;
350                }
351                else
352                {
353                    inputTriGrams.Add(g, 0);
354                }
355            }
356
357            //Union Bigrams
358            HashSet<string> allBigrams = new HashSet<string>(inputBiGrams.Keys);
359            allBigrams.UnionWith(corpusBigrams.Keys);
360
361            //Union Trigrams
362            HashSet<string> allTrigrams = new HashSet<string>(inputTriGrams.Keys);
363            allTrigrams.UnionWith(corpusTrigrams.Keys);
364
365            // Sum of all input Bigrams absolutes
366            double sumBigrams = inputBiGrams.Values.Sum();
367
368            // Sum of all input Trigrams absolutes
369            double sumTrigrams = inputTriGrams.Values.Sum();
370
371            // First part of the equation: Sum up all [K_b (i,j) - D_b (i,j)]
372            double bigramscore = 0.0;
373            foreach (string g in allBigrams)
374            {
375                if (corpusBigrams.ContainsKey(g) && inputBiGrams.ContainsKey(g))
376                {
377                    bigramscore += corpusBigrams[g][1] - inputBiGrams[g] / sumBigrams;
378                }
379                else if (!corpusBigrams.ContainsKey(g))
380                {
381                    bigramscore += 0.0 - inputBiGrams[g] / sumBigrams;
382                }
383                else if (!inputBiGrams.ContainsKey(g))
384                {
385                    bigramscore += corpusBigrams[g][1];
386                }
387            }
388
389            // Second part of the equation: Sum up all [K_t (i,j) - D_t (i,j)]
390            double Trigramscore = 0.0;
391            foreach (string g in allTrigrams)
392            {
393                if (corpusTrigrams.ContainsKey(g) && inputTriGrams.ContainsKey(g))
394                {
395                    Trigramscore += corpusTrigrams[g][1] - inputTriGrams[g] / sumTrigrams;
396                }
397                else if (!corpusTrigrams.ContainsKey(g))
398                {
399                    Trigramscore += 0.0 - inputTriGrams[g] / sumTrigrams;
400                }
401                else if (!inputTriGrams.ContainsKey(g))
402                {
403                    Trigramscore += corpusTrigrams[g][1];
404                }
405            }
406
407            return 10*bigramscore+10*Trigramscore;
408        }//end Execute
409
410        public double regex(string input)
411        {
412            if (settings.RegEx == null)
413            {
414                GuiLogMessage("There is no Regular Expression to be searched for. Please insert regex in the 'Regular Expression' - Textarea", NotificationLevel.Error);
415                return new Double();
416            }
417            try
418            {
419                Match match = Regex.Match(input, settings.RegEx);
420                if (match.Success)
421                {
422                    return 1.0;
423                }
424                else
425                {
426                    return -1.0;
427                }
428            }
429            catch (Exception e)
430            {
431                GuiLogMessage(e.Message, NotificationLevel.Error);
432                return -1.0;
433            }
434
435        }
436
437
438        /// <summary>
439        /// Calculates the Index of Coincidence multiplied with 100 of
440        /// a given byte array
441        ///
442        /// for example a German text has about 7.62
443        ///           an English text has about 6.61
444        /// </summary>
445        /// <param name="text">text to use</param>
446        /// <returns>Index of Coincidence</returns>
447        public double calculateIndexOfCoincidence(byte[] text)
448        {
449            return calculateIndexOfCoincidence(text, text.Length);
450        }
451
452        /// <summary>
453        /// Calculates the Index of Coincidence multiplied with 100 of
454        /// a given byte array
455        ///
456        /// for example a German text has about 7.62
457        ///           an English text has about 6.61
458        /// </summary>
459        /// <param name="text">text to use</param>
460        /// <param name="text">bytesToUse</param>
461        /// <returns>Index of Coincidence</returns>
462        public double calculateIndexOfCoincidence(byte[] text, int bytesToUse)
463        {
464            if (bytesToUse > text.Length)
465                bytesToUse = text.Length;
466
467            double[] n = new double[256];
468            //count all ASCII symbols
469            int counter = 0;
470            foreach (byte b in text)
471            {
472                n[b]++;
473                counter++;
474                if (counter == bytesToUse)
475                    break;
476            }
477
478            double coindex = 0;
479            //sum them
480            for (int i = 0; i < n.Length; i++)
481            {
482                coindex = coindex + n[i] * (n[i] - 1);
483            }
484
485            coindex = coindex / (bytesToUse);
486            coindex = coindex / (bytesToUse - 1);
487
488            return coindex * 100;
489
490        }//end calculateIndexOfCoincidence
491
492
493        private int lastUsedSize = -1;
494        private double[] xlogx;
495        private Mutex prepareMutex = new Mutex();
496
497        private void prepareEntropy(int size)
498        {
499            xlogx = new double[size + 1];
500            //precomputations for fast entropy calculation     
501            xlogx[0] = 0.0;
502            for (int i = 1; i <= size; i++)
503                xlogx[i] = -1.0 * i * Math.Log(i / (double)size) / Math.Log(2.0);
504        }
505
506        /// <summary>
507        /// Calculates the Entropy of a given byte array
508        /// for example a German text has about 4.0629
509        /// </summary>
510        /// <param name="text">text to use</param>
511        /// <returns>Entropy</returns>
512        public double calculateEntropy(byte[] text)
513        {
514            return calculateEntropy(text, text.Length);
515        }
516
517        /// <summary>
518        /// Calculates the Entropy of a given byte array
519        /// for example a German text has about 4.0629
520        /// </summary>
521        /// <param name="text">text to use</param>
522        /// <returns>Entropy</returns>
523        public double calculateEntropy(byte[] text, int bytesToUse)
524        {
525            return NativeCryptography.Crypto.calculateEntropy(text, bytesToUse);
526            if (bytesToUse > text.Length)
527                bytesToUse = text.Length;
528
529            if (lastUsedSize != bytesToUse)
530            {
531                try
532                {
533                    prepareMutex.WaitOne();
534                    if (lastUsedSize != bytesToUse)
535                    {
536                        prepareEntropy(bytesToUse);
537                        lastUsedSize = bytesToUse;
538                    }
539                }
540                finally
541                {
542                    prepareMutex.ReleaseMutex();
543                }
544            }
545
546            int[] n = new int[256];
547            //count all ASCII symbols
548            for (int counter = 0; counter < bytesToUse; counter++)
549            {
550                n[text[counter]]++;
551            }
552
553            double entropy = 0;
554            //calculate probabilities and sum entropy
555            for (int i = 0; i < 256; i++)
556                entropy += xlogx[n[i]];
557
558            return entropy / (double)bytesToUse;
559
560        }//end calculateEntropy
561
562        /// <summary>
563        /// This method calculates a trigram log2 score of a given text on the basis of a given grams dictionary.
564        /// Case is insensitive.
565        /// </summary>
566        /// <param name="input">The text to be scored</param>
567        /// <param name="length">n-gram length</param>
568        /// <returns>The trigram score result</returns>
569        public double calculateNGrams(string input, int length, int valueSelection)
570        {
571            this.statistics = new Dictionary<int, IDictionary<string, double[]>>();
572            double score = 0;
573            if (corpusGrams == null)
574            { corpusGrams = GetStatistics(length); }
575            input = input.ToUpper();
576            // FIXME: case handling?
577
578            HashSet<string> inputGrams = new HashSet<string>();
579
580            foreach (string g in GramTokenizer.tokenize(input, length, false))
581            {
582                // ensure each n-gram is counted only once
583                if (inputGrams.Add(g))
584                {
585                    if (corpusGrams.ContainsKey(g))
586                    {
587                        score += corpusGrams[g][valueSelection];
588
589                    }
590                }
591            }
592
593            return score;
594        }
595        public IDictionary<string, double[]> GetStatistics(int gramLength)
596        {
597            // FIXME: inputTriGrams is not being used!
598
599            // FIXME: implement exception handling
600            if (!statistics.ContainsKey(gramLength))
601            {
602                //GuiLogMessage("Trying to load default statistics for " + gramLength + "-grams", NotificationLevel.Info);
603                statistics[gramLength] = LoadDefaultStatistics(gramLength);
604            }
605
606            return statistics[gramLength];
607        }
608
609        private IDictionary<string, double[]> LoadDefaultStatistics(int length)
610        {
611            txtList = dataMgr.LoadDirectory(DATATYPE);
612
613            return calculateAbsolutes(txtList["2gram.txt"].DataFile.FullName, length);
614        }
615
616        private IDictionary<string, double[]> calculateAbsolutes(String path, int length)
617        {
618
619
620            Dictionary<string, double[]> grams = new Dictionary<string, double[]>();
621            int checkLength;
622            StreamReader reader = new StreamReader(path);
623            String text = reader.ReadToEnd();
624
625            text.ToUpper();
626            text = Regex.Replace(text, "[^A-Z]*", "");
627
628            if (length == 2)
629            {
630                checkLength = text.Length - 1;
631            }
632            else
633            {
634                checkLength = text.Length - 2;
635            }
636            for (int i = 0; i < checkLength; i++)
637            {
638                char a = text[i];
639                char b = text[i + 1];
640                String key;
641                if (length == 3) // Trigrams
642                {
643                    char c = text[i + 2];
644                    key = a.ToString();
645                    key = key + b.ToString();
646                    key = key + c.ToString();
647                }
648                else // Bigrams
649                {
650                    key = a.ToString();
651                    key = key + b.ToString();
652                }
653
654                if (!grams.ContainsKey(key))
655                {
656                    grams.Add(key, new double[] { 1, 0, 0, 0}); 
657                }
658                else
659                {
660                    grams[key][0] = grams[key][0] + 1.0;
661                }
662            }
663
664            double sum = grams.Values.Sum(item => item[ABSOLUTE]);
665            GuiLogMessage("Sum of all n-gram counts is: " + sum, NotificationLevel.Debug);
666
667            // calculate scaled values
668            foreach (double[] g in grams.Values)
669            {
670                g[PERCENTAGED] = g[ABSOLUTE] / sum;
671                g[LOG2] = Math.Log(g[ABSOLUTE], 2);
672                g[SINKOV] = Math.Log(g[PERCENTAGED], Math.E);
673            }
674
675
676
677            return grams;
678        }
679
680        public string ByteArrayToString(byte[] arr)
681        {
682            System.Text.ASCIIEncoding enc = new System.Text.ASCIIEncoding();
683            return enc.GetString(arr);
684        }
685
686
687        #endregion
688
689
690    }
691
692    #region slave
693
694    public class CostFunctionControl : IControlCost
695    {
696        public event IControlStatusChangedEventHandler OnStatusChanged;
697        #region IControlCost Members
698
699        private CostFunction plugin;
700
701        #endregion
702
703        /// <summary>
704        /// Constructor
705        /// </summary>
706        /// <param name="plugin"></param>
707        public CostFunctionControl(CostFunction plugin)
708        {
709            this.plugin = plugin;
710        }
711
712        public int getBytesToUse()
713        {
714            try
715            {
716                return int.Parse(((CostFunctionSettings)this.plugin.Settings).BytesToUse);
717            }
718            catch (Exception ex)
719            {
720                throw new Exception("Entered bytesToUse is not an integer: " + ex.Message);
721            }
722        }
723
724        /// <summary>
725        /// Returns the relation operator of the cost function which is set by by CostFunctionSettings
726        /// </summary>
727        /// <returns>RelationOperator</returns>
728        public RelationOperator getRelationOperator()
729        {
730            switch (((CostFunctionSettings)this.plugin.Settings).FunctionType)
731            {
732                case 0: //Index of coincidence
733                    return RelationOperator.LargerThen;
734                case 1: //Entropy
735                    return RelationOperator.LessThen;
736                case 2: // Bigrams: log 2
737                    return RelationOperator.LessThen;
738                case 3: // Sinkov
739                    return RelationOperator.LargerThen;
740                case 4: // percentage
741                    return RelationOperator.LargerThen;
742                case 5: // Regular Expression
743                    return RelationOperator.LargerThen;
744                case 6: // Weighted Bigrams/Trigrams
745                    return RelationOperator.LargerThen;
746
747                default:
748                    throw new NotImplementedException("The value " + ((CostFunctionSettings)this.plugin.Settings).FunctionType + " is not implemented.");
749            }//end switch
750        }//end getRelationOperator
751
752        /// <summary>
753        /// Calculates the cost function of the given text
754        ///
755        /// Cost function can be set by CostFunctionSettings
756        /// This algorithm uses a bytesToUse which can be set by CostFunctionSettings
757        /// If bytesToUse is set to 0 it uses the whole text
758        ///
759        /// </summary>
760        /// <param name="text"></param>
761        /// <returns>cost</returns>
762        public double calculateCost(byte[] text)
763        {
764            int bytesToUse = 0;
765            try
766            {
767                bytesToUse = ((CostFunctionSettings)this.plugin.Settings).BytesToUseInteger;
768            }
769            catch (Exception ex)
770            {
771                throw new Exception("Entered bytesToUse is not an integer: " + ex.Message);
772            }
773
774            switch (((CostFunctionSettings)this.plugin.Settings).FunctionType)
775            {
776                case 0: //Index of coincidence
777                    return plugin.calculateIndexOfCoincidence(text, bytesToUse);
778                case 1: //Entropy
779                    return plugin.calculateEntropy(text, bytesToUse);
780                case 2: // Bigrams: log 2
781                    return plugin.calculateNGrams(plugin.ByteArrayToString(text), 2, 2);
782                case 3: // Bigrams: Sinkov
783                    return plugin.calculateNGrams(plugin.ByteArrayToString(text), 2, 3);
784                case 4: // Bigrams: Percentaged
785                    return plugin.calculateNGrams(plugin.ByteArrayToString(text), 2, 1);
786                case 5: // regular expression
787                    return plugin.regex(plugin.ByteArrayToString(text));
788                case 6:
789                    return plugin.calculateWeighted(plugin.ByteArrayToString(text));
790                default:
791                    throw new NotImplementedException("The value " + ((CostFunctionSettings)this.plugin.Settings).FunctionType + " is not implemented.");
792            }//end switch
793        }
794
795
796    #endregion
797    }
798
799}
800
Note: See TracBrowser for help on using the repository browser.